oj.uz

Submission #137479

# Submission time Handle Problem Language Result Execution time Memory
137479 2019-07-28T02:19:40 Z silxikys Hacker (BOI15_hac) C++14
20 / 100
 706 ms 111608 KB 
#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';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory 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

Subtask #2
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #3
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #4
0 / 40.0

# Verdict Execution time Memory 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 -