Submission #994318


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = 1000000007;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef pair<int,int> P;
typedef long long ll;

const ll INF = ((ll)1)<<50;

ll A[200002];
ll cumsum[200002];
ll X[200002];
ll N, M;

// turn = 0 -> snuke's turn
ll memo[200002][2];
ll dfs(int pos, int turn){
    if(pos == N - 2) return 0;
    if(memo[pos][turn] != -1) return memo[pos][turn];
    ll ret = -INF;
    for(int i=pos+2;i<N;i++){
        int diff = A[i] - (cumsum[i - 1] - cumsum[pos + 1]);
        ret = max(ret, diff - dfs(i - 1, (turn + 1) % 2));
    }
    memo[pos][turn] = ret;
    return ret;
}


int main(){
    cin >> N;
    for(int i=0;i<N - 1;i++){
        cin >> A[i];
        if(i == 0) cumsum[i] = A[i];
        else cumsum[i] = cumsum[i - 1] + A[i];
    }
    cin >> M;
    for(int i=0;i<M;i++){
        cin >> X[i];
    }

    for(int i=0;i<M;i++){
        if(i != 0){
            cout << 0 << endl;
            continue;
        }
        memset(memo, -1, sizeof(memo));
        A[N - 1] = X[0];
        cout << A[0] - A[1] + dfs(0, 0) << endl;
    }
    
    return 0;
}

Submission Info

Submission Time
Task H - Tokaido
User zaburo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1188 Byte
Status WA
Exec Time 2103 ms
Memory 23680 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 0 / 700 0 / 900
Status
AC × 1
WA × 1
AC × 4
TLE × 16
AC × 4
WA × 4
TLE × 29
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt
Case Name Status Exec Time Memory
01-01.txt TLE 2103 ms 22144 KB
01-02.txt AC 5 ms 3328 KB
01-03.txt AC 18 ms 3584 KB
01-04.txt TLE 2103 ms 12160 KB
01-05.txt TLE 2103 ms 22144 KB
01-06.txt TLE 2103 ms 22272 KB
01-07.txt TLE 2102 ms 8704 KB
01-08.txt TLE 2103 ms 22016 KB
01-09.txt TLE 2103 ms 22144 KB
01-10.txt AC 6 ms 3328 KB
01-11.txt TLE 2102 ms 6912 KB
01-12.txt TLE 2103 ms 21376 KB
01-13.txt TLE 2103 ms 22144 KB
01-14.txt TLE 2103 ms 22016 KB
01-15.txt TLE 2103 ms 22144 KB
01-16.txt TLE 2103 ms 22144 KB
01-17.txt TLE 2103 ms 22144 KB
01-18.txt TLE 2103 ms 22144 KB
01-19.txt TLE 2103 ms 22144 KB
02-01.txt TLE 2102 ms 6656 KB
02-02.txt TLE 2103 ms 23680 KB
02-03.txt TLE 2103 ms 23680 KB
02-04.txt TLE 2103 ms 23680 KB
02-05.txt WA 916 ms 5376 KB
02-06.txt TLE 2103 ms 23680 KB
02-07.txt TLE 2103 ms 23680 KB
02-08.txt WA 907 ms 5376 KB
02-09.txt WA 913 ms 5504 KB
02-10.txt TLE 2102 ms 14336 KB
02-11.txt TLE 2103 ms 23680 KB
02-12.txt TLE 2103 ms 23296 KB
02-13.txt TLE 2103 ms 23680 KB
02-14.txt TLE 2103 ms 23680 KB
02-15.txt TLE 2103 ms 23680 KB
02-16.txt TLE 2103 ms 23680 KB
sample-01.txt AC 6 ms 3328 KB
sample-02.txt WA 6 ms 3328 KB