Submission #00384

ソースコード

?
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[1010][1010];
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 == 1000 && t == 1000) return dp[s][t] = 0;
if((s + t) % 2 == 0 && (s >= 1001 || t >= 1001)) return dp[s][t] = INF;
if((s + t) % 2 == 1 && (s >= 1001 || t >= 1001)) 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 <= 1005;i++){
for(int j = 0;j <= 1005;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:04:12
言語 C++11
状態 Wrong Answer
得点 60
ソースコード長 2886 Byte
最大実行時間 365 ms
最大メモリ使用量 40356 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 75 ms 40160 KB
1
2
3
4
!test_02.txt AC 74 ms 40160 KB
1
2
3
4
!test_03.txt AC 76 ms 40040 KB
1
2
3
4
randL_01.txt WA 207 ms 40048 KB
1
randL_02.txt WA 365 ms 40184 KB
1
randL_03.txt WA 355 ms 40184 KB
1
randL_04.txt WA 350 ms 40188 KB
1
randL_05.txt WA 349 ms 40192 KB
1
randM_01.txt AC 77 ms 40188 KB
1
3
randM_02.txt AC 83 ms 40192 KB
1
3
randM_03.txt AC 88 ms 40192 KB
1
3
randM_04.txt AC 90 ms 40200 KB
1
3
randM_05.txt AC 93 ms 40208 KB
1
3
randS_01.txt AC 75 ms 40212 KB
1
2
3
randS_02.txt AC 74 ms 40212 KB
1
2
3
randS_03.txt AC 77 ms 40212 KB
1
2
3
randS_04.txt AC 70 ms 40212 KB
1
2
3
randS_05.txt AC 79 ms 40208 KB
1
2
3
randT_01.txt AC 75 ms 40212 KB
1
2
3
4
randT_02.txt AC 70 ms 40220 KB
1
2
3
4
randT_03.txt AC 78 ms 40220 KB
1
2
3
4
randT_04.txt AC 71 ms 40356 KB
1
2
3
4
randT_05.txt AC 79 ms 40228 KB
1
2
3
4