oj.uz

Submission #34444

# Submission time Handle Problem Language Result Execution time Memory
34444 2017-11-11T10:51:18 Z Extazy Hacker (BOI15_hac) C++14
0 / 100
 0 ms 1840 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define prev akhgjlkqhgjkq
#define next ohquoghqkjhgjkq

using namespace std;

const int N = 312;
const int INF = (1e9) + 7;

int n,a[N];
bool used[N][N][N][2];
int state[N][N][N][2];
int ans;

int length(int from, int to) {
    if(from<=to) return to-from+1;
    else return n-from+1+to;
}

bool is_in(int from, int to, int x) {
    if(from<=to) return from<=x && x<=to;
    else return x>=from || x<=to;
}

int prev(int x) {
    return x==1 ? n : x-1;
}

int next(int x) {
    return x==n ? 1 : x+1;
}

int recurse(int fromb, int tob, int froms, int tos, int who) {
    if(length(fromb,tob)+length(froms,tos)==n) return 0;
    if(used[fromb][tob][froms][who]) return state[fromb][tob][froms][who];
    
    if(fromb<0 || tob<0 || froms<0 || tos<0 || who<0 || fromb>n || tob>n || froms>n || tos>n || who>1) while(1) {}

    used[fromb][tob][froms][who]=true;

    if(who==0) { //Byteasar's turn
        int ans=0;

        //Let's take the one on the left
        if(!is_in(froms,tos,prev(fromb))) ans=max(ans,a[prev(fromb)]+recurse(prev(fromb),tob,froms,tos,1));
        
        //Let's take the one on the right
        if(!is_in(froms,tos,next(tob))) ans=max(ans,a[next(tob)]+recurse(fromb,next(tob),froms,tos,1));
        
        return state[fromb][tob][froms][who]=ans;
    }

    else { //System's turn
        int ans=INF;

        //Let's take the one on the left
        if(!is_in(fromb,tob,prev(froms))) ans=min(ans,recurse(fromb,tob,prev(froms),tos,0));

        //Let's take the one on the right
        if(!is_in(fromb,tob,next(tos))) ans=min(ans,recurse(fromb,tob,froms,next(tos),0));
        
        return state[fromb][tob][froms][who]=ans;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j;

    scanf("%d", &n);
    if(n<0 || n>300) while(1) {}
    for(i=1;i<=n;i++) {
        scanf("%d", &a[i]);
    }

    //Looking for Byteasar's first move
    for(i=1;i<=n;i++) {
        int mn=INF;

        //Looking for System's first move
        for(j=1;j<=n;j++) if(i!=j) {
            mn=min(mn,recurse(i,i,j,j,0)+a[i]);
        }

        ans=max(ans,mn);
    }

    printf("%d\n", ans);

    return 0;
}

Compilation message

hac.cpp: In function 'int main()':
hac.cpp:72:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
hac.cpp:75:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
                           ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -