Submission #00387

ソースコード

?
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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w
using namespace std;
#define int long long
//typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef pair<int,int> P;
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
struct edge{ int to, cost; };
int h,w,a,b,c,d,x[2005][2005],dp[2010][2010];
int calc(int s,int t,int u,int v){
s--;t--;
if(s > u || t > v || u < 0 || v < 0 || s > 2000 || t > 2000) return 0;
s = max(0ll,s);
t = max(0ll,t);
u = min(2000ll,u);
v = min(2000ll,v);
return x[u][v] - x[u][t] - x[s][v] + x[s][t];
}
int dfs(int s,int t){
if(dp[s][t] != -1) return dp[s][t];
if(s == 2000 && t == 2000) return dp[s][t] = 0;
if((s + t) % 2 == 0 && (s >= 2001 || t >= 2001)) return dp[s][t] = INF;
if((s + t) % 2 == 1 && (s >= 2001 || t >= 2001)) return dp[s][t] = -INF;
int na = 0,nb = 0;
na += calc(a - s,b - s,a + s,b + s) - calc(a - s + 1,b - s + 1,a + s - 1,b + s - 1);
int x1 = max(a - s,c - t + 1),x2 = min(a + s,c + t - 1),y1 = max(b - s,d - t + 1),y2 = min(b + s,d + t - 1);
if(x1 <= x2 && y1 <= y2) na -= calc(x1,y1,x2,y2);
x1 = max(a - s + 1,c - t + 1),x2 = min(a + s - 1,c + t - 1),y1 = max(b - s + 1,d - t + 1),y2 = min(b + s - 1,d + t - 1);
if(x1 <= x2 && y1 <= y2) na += calc(x1,y1,x2,y2);
nb += calc(c - t,d - t,c + t,d + t) - calc(c - t + 1,d - t + 1,c + t - 1,d + t - 1);
x1 = max(a - s + 1,c - t),x2 = min(a + s - 1,c + t),y1 = max(b - s + 1,d - t),y2 = min(b + s - 1,d + t);
if(x1 <= x2 && y1 <= y2) nb -= calc(x1,y1,x2,y2);
x1 = max(a - s + 1,c - t + 1),x2 = min(a + s - 1,c + t - 1),y1 = max(b - s + 1,d - t + 1),y2 = min(b + s - 1,d + t - 1);
if(x1 <= x2 && y1 <= y2) nb += calc(x1,y1,x2,y2);
na += dfs(s + 1,t);
nb += dfs(s,t + 1);
if((s + t) % 2 == 0) return dp[s][t] = max(na,nb);
else return dp[s][t] = min(dfs(s + 1,t),dfs(s,t + 1));
}
signed main(){
cin >> h >> w >> a >> b >> c >> d;
int s = a + b,t = a - b + 1000;
a = s;
b = t;
s = c + d;t = c - d + 1000;
c = s;
d = t;
for(int i = 0;i <= 2005;i++){
for(int j = 0;j <= 2005;j++) dp[i][j] = -1;
}
for(int i = 1;i <= h;i++){
for(int j = 1;j <= w;j++) cin >> x[i + j][i - j + 1000];
}
for(int i = 1;i <= 2000;i++){
x[i][0] += x[i - 1][0];
x[0][i] += x[0][i - 1];
}
for(int i = 1;i <= 2000;i++){
for(int j = 1;j <= 2000;j++) x[i][j] += x[i - 1][j] + x[i][j - 1] - x[i - 1][j - 1];
}
cout << dfs(0,0) << endl;
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
!test_01.txt AC 204 ms 64096 KB
1
2
3
4
!test_02.txt AC 212 ms 64096 KB
1
2
3
4
!test_03.txt AC 210 ms 64096 KB
1
2
3
4
randL_01.txt TLE 1000 ms 64096 KB
1
randL_02.txt AC 498 ms 63972 KB
1
randL_03.txt AC 489 ms 64224 KB
1
randL_04.txt AC 476 ms 64100 KB
1
randL_05.txt AC 495 ms 64228 KB
1
randM_01.txt AC 212 ms 64104 KB
1
3
randM_02.txt AC 220 ms 64228 KB
1
3
randM_03.txt AC 217 ms 64224 KB
1
3
randM_04.txt AC 224 ms 64220 KB
1
3
randM_05.txt AC 215 ms 64212 KB
1
3
randS_01.txt AC 208 ms 64216 KB
1
2
3
randS_02.txt AC 204 ms 64216 KB
1
2
3
randS_03.txt AC 203 ms 64212 KB
1
2
3
randS_04.txt AC 210 ms 64216 KB
1
2
3
randS_05.txt AC 204 ms 64084 KB
1
2
3
randT_01.txt AC 207 ms 64088 KB
1
2
3
4
randT_02.txt AC 211 ms 64088 KB
1
2
3
4
randT_03.txt AC 204 ms 64088 KB
1
2
3
4
randT_04.txt AC 203 ms 64212 KB
1
2
3
4
randT_05.txt AC 211 ms 64212 KB
1
2
3
4