Submission #1607339
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
//#define int long long
#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
int n, m;
int a[55], b[55];
int dp[52][52][52][52][2][2];
int calc(int da, int db, int sa, int sb, int tn) {
if (sa == 0 && sb == 0) return 0;
int i = n - 1 - da;
int j = m - 1 - db;
bool checka = false, checkb = false;
int ret = 0;
if (sb == 0) {
while (i > (n - 1 - da - sa)) {
if (a[i] != -1) ret += a[i];
i--;
}
return ret;
}
if (sa == 0) {
while(j > (m - 1 - db - sb)) {
if (b[j] != -1) ret -= b[j];
j--;
}
return ret;
}
while (i > (n - 1 - da - sa) && j > (m - 1 - db - sb)) {
if (tn == 1) {
if (a[i] == -1) checkb = true;
else if (!checka) ret += a[i];
if (b[j] == -1) checka = true;
else if (!checkb) ret -= b[j];
i--; j--;
}
else {
if (b[j] == -1) checka = true;
else if (!checkb) ret -= b[j];
if (a[i] == -1) checkb = true;
else if (!checka) ret += a[i];
i--; j--;
}
}
if (!checka) {
while (i > (n - 1 - da - sa)) {
if (a[i] != -1) ret += a[i];
i--;
}
}
if (!checkb) {
while (j > (m - 1 - db - sb)) {
if (b[j] != -1) ret -= b[j];
j--;
}
}
return ret;
}
int dfs(int da, int db, int sa, int sb, int tn, int cnt) {
if ((dp[da][db][sa][sb][tn][cnt] != INF) && (dp[da][db][sa][sb][tn][cnt] != -INF)) return dp[da][db][sa][sb][tn][cnt];
if (da == 0 && db == 0) {
if (tn == 0) return (dp[da][db][sa][sb][tn][cnt] = max(dp[da][db][sa][sb][tn][cnt], calc(da, db, sa, sb, tn)));
else return (dp[da][db][sa][sb][tn][cnt] = min(dp[da][db][sa][sb][tn][cnt], calc(da, db, sa, sb, tn)));
}
if (da == 0 && tn == 0) {
if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][0][cnt] = max(0, dp[da][db][sa][sb][0][cnt]));
if (sa == 0 && sb == 0) dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], dfs(da, db, 0, 0, 1, 1));
else dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], calc(da, db, sa, sb, tn) + dfs(da, db, 0, 0, 1, 0));
return dp[da][db][sa][sb][0][cnt];
}
else if (db == 0 && tn == 1) {
if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][1][cnt] = min(0, dp[da][db][sa][sb][1][cnt]));
if (sa == 0 && sb == 0) dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], dfs(da, db, 0, 0, 0, 1));
else dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], calc(da, db, sa, sb, tn) + dfs(da, db, 0, 0, 0, 0));
return dp[da][db][sa][sb][1][cnt];
}
if (tn == 0) {
dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], dfs(da - 1, db, sa + 1, sb, 1, 0));
if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][0][cnt] = max(0, dp[da][db][sa][sb][0][cnt]));
int tmp = calc(da, db, sa, sb, tn);
if (sa == 0 && sb == 0) dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], tmp + dfs(da, db, 0, 0, 1, 1));
else dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], tmp + dfs(da, db, 0, 0, 1, 0));
return dp[da][db][sa][sb][0][cnt];
}
else {
dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], dfs(da, db - 1, sa, sb + 1, 0, 0));
if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][1][cnt] = min(0, dp[da][db][sa][sb][1][cnt]));
int tmp = calc(da, db, sa, sb, tn);
if (sa == 0 && sb == 0) dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], tmp + dfs(da, db, 0, 0, 0, 1));
else dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], tmp + dfs(da, db, 0, 0, 0, 0));
return dp[da][db][sa][sb][1][cnt];
}
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
rep(i, n) cin >> a[i];
rep(i, m) cin >> b[i];
rep(i, n + 1)rep(j, m + 1)rep(k, n + 1)rep(l, m + 1)rep(o, 2) {
dp[i][j][k][l][0][o] = -INF;
dp[i][j][k][l][1][o] = INF;
}
cout << dfs(n, m, 0, 0, 0, 0) << endl;
}
Submission Info
Submission Time |
|
Task |
D - インビジブル |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
5469 Byte |
Status |
AC |
Exec Time |
50 ms |
Memory |
112896 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_00, 00_sample_01, 00_sample_02, 30_random_small_000, 30_random_small_001, 30_random_small_002, 30_random_small_003, 30_random_small_004, 30_random_small_005, 30_random_small_006, 30_random_small_007, 30_random_small_008, 30_random_small_009, 31_random_skewed_000, 31_random_skewed_001, 31_random_skewed_002, 31_random_skewed_003, 31_random_skewed_004, 32_random_skewed_000, 32_random_skewed_001, 32_random_skewed_002, 32_random_skewed_003, 32_random_skewed_004, 33_random_frequent_invisible_000, 33_random_frequent_invisible_001, 33_random_frequent_invisible_002, 33_random_frequent_invisible_003, 33_random_frequent_invisible_004, 35_random_all_invisible_000, 36_random_all_same_score_000, 37_increasing_000, 38_decreasing_000, 40_random_max_000, 40_random_max_001, 40_random_max_002, 40_random_max_003, 40_random_max_004 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
2 ms |
4352 KB |
00_sample_01 |
AC |
2 ms |
6400 KB |
00_sample_02 |
AC |
2 ms |
8448 KB |
30_random_small_000 |
AC |
4 ms |
18816 KB |
30_random_small_001 |
AC |
4 ms |
12544 KB |
30_random_small_002 |
AC |
2 ms |
6528 KB |
30_random_small_003 |
AC |
2 ms |
8576 KB |
30_random_small_004 |
AC |
2 ms |
10496 KB |
30_random_small_005 |
AC |
3 ms |
10624 KB |
30_random_small_006 |
AC |
2 ms |
6528 KB |
30_random_small_007 |
AC |
2 ms |
6528 KB |
30_random_small_008 |
AC |
1 ms |
2304 KB |
30_random_small_009 |
AC |
1 ms |
2304 KB |
31_random_skewed_000 |
AC |
23 ms |
109312 KB |
31_random_skewed_001 |
AC |
23 ms |
109312 KB |
31_random_skewed_002 |
AC |
23 ms |
109184 KB |
31_random_skewed_003 |
AC |
22 ms |
108928 KB |
31_random_skewed_004 |
AC |
23 ms |
109312 KB |
32_random_skewed_000 |
AC |
6 ms |
21376 KB |
32_random_skewed_001 |
AC |
2 ms |
4608 KB |
32_random_skewed_002 |
AC |
5 ms |
19200 KB |
32_random_skewed_003 |
AC |
2 ms |
4608 KB |
32_random_skewed_004 |
AC |
2 ms |
4608 KB |
33_random_frequent_invisible_000 |
AC |
11 ms |
51712 KB |
33_random_frequent_invisible_001 |
AC |
30 ms |
112128 KB |
33_random_frequent_invisible_002 |
AC |
23 ms |
89344 KB |
33_random_frequent_invisible_003 |
AC |
7 ms |
31104 KB |
33_random_frequent_invisible_004 |
AC |
4 ms |
14976 KB |
35_random_all_invisible_000 |
AC |
5 ms |
17152 KB |
36_random_all_same_score_000 |
AC |
45 ms |
112896 KB |
37_increasing_000 |
AC |
45 ms |
112896 KB |
38_decreasing_000 |
AC |
45 ms |
112896 KB |
40_random_max_000 |
AC |
50 ms |
112896 KB |
40_random_max_001 |
AC |
49 ms |
112896 KB |
40_random_max_002 |
AC |
49 ms |
112896 KB |
40_random_max_003 |
AC |
49 ms |
112896 KB |
40_random_max_004 |
AC |
50 ms |
112896 KB |