#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5e5+5;
const int INF = 2e9+9;
int n, v[maxn];
int dp[305][305][305]; //# plies
void amax(int& a, int b) {
a = max(a,b);
}
void amin(int& a, int b) {
a = min(a,b);
}
int f(int t, int i, int j) {
if (dp[t][i][j] >= 0) return dp[t][i][j];
int ir = (i+(t+1)/2) % n;
int jr = (j+t/2) % n;
//[i,ir], [j,jr]
if (j == ((ir+1) % n) && (i == ((jr+1) % n))) {
return dp[t][i][j] = 0;
}
if (t % 2 == 0) {
//i's turn
dp[t][i][j] = 0;
if ((ir+1)% n != j) {
amax(dp[t][i][j],f(t+1,i,j) + v[(ir+1)%n]);
}
else if ((i-1+n)%n != jr) {
amax(dp[t][i][j],f(t+1,(i-1+n)%n,j) + v[(i-1+n)%n]);
}
if (t == 0) {
dp[t][i][j] += v[i];
}
//printf("[%d, %d], [%d, %d]\n",i,ir,j,jr);
//printf("[%d][%d][%d]: %d\n",t,i,j,dp[t][i][j]);
return dp[t][i][j];
}
else {
//j's turn
dp[t][i][j] = INF;
if ((jr+1) % n != i) {
amin(dp[t][i][j],f(t+1,i,j));
}
else if ((j-1+n)%n != ir) {
amin(dp[t][i][j],f(t+1,i,(j-1+n)%n));
}
assert(dp[t][i][j] != INF);
//printf("[%d, %d], [%d, %d]\n",i,ir,j,jr);
//printf("[%d][%d][%d]: %d\n",t,i,j,dp[t][i][j]);
return dp[t][i][j];
}
}
int main()
{
//ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];
memset(dp,-1,sizeof dp);
int ans = 0;
for (int i = 0; i < n; i++) {
int curr = INF;
for (int j = 0; j < n; j++) {
if (i == j) continue;
amin(curr,f(0,i,j));
}
ans = max(ans,curr);
}
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
111352 KB |
Output is correct |
2 |
Correct |
94 ms |
111480 KB |
Output is correct |
3 |
Correct |
94 ms |
111352 KB |
Output is correct |
4 |
Correct |
105 ms |
111440 KB |
Output is correct |
5 |
Correct |
109 ms |
111352 KB |
Output is correct |
6 |
Correct |
109 ms |
111336 KB |
Output is correct |
7 |
Correct |
501 ms |
111480 KB |
Output is correct |
8 |
Correct |
521 ms |
111352 KB |
Output is correct |
9 |
Correct |
470 ms |
111472 KB |
Output is correct |
10 |
Correct |
478 ms |
111480 KB |
Output is correct |
11 |
Correct |
479 ms |
111508 KB |
Output is correct |
12 |
Correct |
473 ms |
111608 KB |
Output is correct |
13 |
Correct |
113 ms |
111384 KB |
Output is correct |
14 |
Correct |
94 ms |
111352 KB |
Output is correct |
15 |
Correct |
95 ms |
111352 KB |
Output is correct |
16 |
Correct |
470 ms |
111456 KB |
Output is correct |
17 |
Correct |
468 ms |
111352 KB |
Output is correct |
18 |
Correct |
470 ms |
111608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
111352 KB |
Output is correct |
2 |
Correct |
94 ms |
111480 KB |
Output is correct |
3 |
Correct |
94 ms |
111352 KB |
Output is correct |
4 |
Correct |
105 ms |
111440 KB |
Output is correct |
5 |
Correct |
109 ms |
111352 KB |
Output is correct |
6 |
Correct |
109 ms |
111336 KB |
Output is correct |
7 |
Correct |
501 ms |
111480 KB |
Output is correct |
8 |
Correct |
521 ms |
111352 KB |
Output is correct |
9 |
Correct |
470 ms |
111472 KB |
Output is correct |
10 |
Correct |
478 ms |
111480 KB |
Output is correct |
11 |
Correct |
479 ms |
111508 KB |
Output is correct |
12 |
Correct |
473 ms |
111608 KB |
Output is correct |
13 |
Correct |
113 ms |
111384 KB |
Output is correct |
14 |
Correct |
94 ms |
111352 KB |
Output is correct |
15 |
Correct |
95 ms |
111352 KB |
Output is correct |
16 |
Correct |
470 ms |
111456 KB |
Output is correct |
17 |
Correct |
468 ms |
111352 KB |
Output is correct |
18 |
Correct |
470 ms |
111608 KB |
Output is correct |
19 |
Incorrect |
706 ms |
111440 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
111480 KB |
Output is correct |
2 |
Incorrect |
586 ms |
111352 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
111352 KB |
Output is correct |
2 |
Correct |
94 ms |
111480 KB |
Output is correct |
3 |
Correct |
94 ms |
111352 KB |
Output is correct |
4 |
Correct |
105 ms |
111440 KB |
Output is correct |
5 |
Correct |
109 ms |
111352 KB |
Output is correct |
6 |
Correct |
109 ms |
111336 KB |
Output is correct |
7 |
Correct |
501 ms |
111480 KB |
Output is correct |
8 |
Correct |
521 ms |
111352 KB |
Output is correct |
9 |
Correct |
470 ms |
111472 KB |
Output is correct |
10 |
Correct |
478 ms |
111480 KB |
Output is correct |
11 |
Correct |
479 ms |
111508 KB |
Output is correct |
12 |
Correct |
473 ms |
111608 KB |
Output is correct |
13 |
Correct |
113 ms |
111384 KB |
Output is correct |
14 |
Correct |
94 ms |
111352 KB |
Output is correct |
15 |
Correct |
95 ms |
111352 KB |
Output is correct |
16 |
Correct |
470 ms |
111456 KB |
Output is correct |
17 |
Correct |
468 ms |
111352 KB |
Output is correct |
18 |
Correct |
470 ms |
111608 KB |
Output is correct |
19 |
Incorrect |
706 ms |
111440 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |