Submission #00377

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// see https://gist.github.com/LumaKernel/ff55d49ee1af69b7388f15b707e75c15
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
typedef vector<int> VI;
typedef vector<P> VP;
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RREP(i,n) RFOR(i,0,n)
#define LFOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RLFOR(i,b,a) for(ll i=(b)-1;i>=(a);--i)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define PB push_back
#define EACH(i,c) REP(i,(int)(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define dump(x) //cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";
#define dump2(x,y) //cerr << "[L " << __LINE__ << "] " << #x << " = " << (x)\
<< " , " << #y << " = " << (y) << "\n";
const ll INF = 1e18;
const double EPS = 1e-10;
int n,m,h,w,a,b,c,d;
int f[2000][2000];
ll dpP[2001][2001],dpQ[2001][2001];
#define isInside(x, y) (0<=(x)&&(x)<w&&0<=(y)&&(y)<h)
ll point(int isA, int _cA, int i){
int cA = _cA, cQ = i - cA;
dump(cQ);
int ay=a,ax=b,cy=c,cx=d;
if(!isA) {
swap(cA, cQ);
dump(cA);
swap(ax,cx);
swap(ay,cy);
dump(cA);
}
dump(cA);
cA--;cQ--;
dump(cA);
ll res = 0;
FOR(c, -cA, cA+1){
REP(rev, 2) if(!rev || (c != -cA && c != cA)){
int x = ax + c;
int y = ay + (cA - abs(c)) * (rev ? 1 : -1);
dump2(y,x);
if(!isInside(x, y)) continue;
dump(1);
int dQ = abs(x-cx)+abs(y-cy);
if(dQ<=cQ) continue;
dump(2);
res += f[y][x];
// dump2(y,x);
dump2(dQ,cQ);
dump(f[y][x]);
}
}
return res;
}
void solve(int pTurn, int i, int chosenA){
if(dpP[i][chosenA]!=-INF) return;
solve(!pTurn, i+1, chosenA+1); // chose A
solve(!pTurn, i+1, chosenA); // chose C
ll xA = point(1,chosenA+1, i+1); // point if choose A
ll xC = point(0,chosenA, i+1); // point if choose C
dump2(i,chosenA);
dump2(xA,xC);
ll sA,sC;
sA = (pTurn ? dpP : dpQ)[i+1][chosenA+1] + xA;
sC = (pTurn ? dpP : dpQ)[i+1][chosenA] + xC;
dump2(sA-xA, xC-sC);
(pTurn ? dpP : dpQ) [i][chosenA] = max(sA, sC);
(!pTurn ? dpP : dpQ) [i][chosenA] =
(!pTurn ? dpP : dpQ) [i+1][chosenA + (sA > sC ? 1 : 0)];
}
int main() {
omajinai;
cin>>h>>w>>a>>b>>c>>d;
a--;b--;c--;d--;
REP(i,h)REP(j,w){
cin>>f[i][j];
}
REP(i, 2000)REP(j, 2000) dpP[i][j] = -INF;
REP(i, h+w+1) dpP[h+w][i] = 0;
solve(1, 0, 0);
dump(point(0,1,2+1));
cout << dpP[0][0] << endl;
}

ステータス

項目 データ
問題 0005 - 2buttons
ユーザー名 luma
投稿日時 2017-11-26 14:57:09
言語 C++11
状態 Time Limit Exceeded
得点 0
ソースコード長 2940 Byte
最大実行時間 1000 ms
最大メモリ使用量 47828 KB

セット

セット 得点 Cases
1 ALL 0 / 40 *
2 partial_2 0 / 20 !*, *T*, *S*
3 partial_3 0 / 20 !*, *T*, *S*, *M*
4 partial_1 0 / 20 !*, *T*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
!test_01.txt AC 25 ms 33248 KB
1
2
3
4
!test_02.txt AC 20 ms 33316 KB
1
2
3
4
!test_03.txt AC 23 ms 33264 KB
1
2
3
4
randL_01.txt TLE 1000 ms 47780 KB
1
randL_02.txt TLE 1000 ms 47736 KB
1
randL_03.txt TLE 1000 ms 47828 KB
1
randL_04.txt TLE 1000 ms 47796 KB
1
randL_05.txt TLE 1000 ms 47752 KB
1
randM_01.txt WA 171 ms 41956 KB
1
3
randM_02.txt WA 164 ms 41948 KB
1
3
randM_03.txt WA 170 ms 42064 KB
1
3
randM_04.txt WA 188 ms 41924 KB
1
3
randM_05.txt WA 165 ms 42040 KB
1
3
randS_01.txt WA 23 ms 33708 KB
1
2
3
randS_02.txt AC 23 ms 33752 KB
1
2
3
randS_03.txt WA 24 ms 33800 KB
1
2
3
randS_04.txt WA 29 ms 33844 KB
1
2
3
randS_05.txt WA 26 ms 33760 KB
1
2
3
randT_01.txt WA 22 ms 33412 KB
1
2
3
4
randT_02.txt AC 20 ms 33464 KB
1
2
3
4
randT_03.txt AC 24 ms 33508 KB
1
2
3
4
randT_04.txt WA 19 ms 33428 KB
1
2
3
4
randT_05.txt WA 26 ms 33480 KB
1
2
3
4