Submission #1351973


Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

typedef pair<int, int> pii;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

int N, M, a[60], b[60];
int suma[60], sumb[60];
// memo[s][t][u][v][turn][pass] :=
//      a についてスタックが [s, t) の範囲、
//      b についてスタックが [u, v) の範囲、
//      turn と pass の情報
//      この時の point_a - point_b の値
int memo[60][60][60][60][2][3];

// pass は連続したパスの回数を指す
int dfs(int s, int t, int u, int v, int turn, int pass) {
    int& val = memo[s][t][u][v][turn][pass];
    if(val != -INF) return val;

    // 今のスタックの状態で起こる得点差
    val =  suma[t] - suma[s];
    val -= sumb[v] - sumb[u];

    // 終了条件でなければ pass 可能
    // パスすることによってスタックは空になる
    // 以降の操作で得られる得点差をもらってくる
    if(!(s == t && u == v && pass == 1)) {
        if(s == t && u == v) val += dfs(t, t, v, v, turn^1, pass+1);
        else val += dfs(t, t, v, v, turn^1, 0);
    }

    // take (first)
    if(turn == 0) {
        if(t < N) {
            // 妨害 -> 現在スタックにある相手のカード全てが取れなくなる
            //      -> つまり相手スタックが空になるのと同じ
            if(a[t] == -1) chmax(val, dfs(s, t+1, v, v, turn^1, 0));
            else           chmax(val, dfs(s, t+1, u, v, turn^1, 0));
        }
    }
    // take (second)
    else {
        if(v < M) {
            if(b[v] == -1) chmin(val, dfs(t, t, u, v+1, turn^1, 0));
            else           chmin(val, dfs(s, t, u, v+1, turn^1, 0));
        }
    }
    return val;
}

signed main() {
    rep(i,0,60) rep(j,0,60) rep(k,0,60) rep(l,0,60) rep(t,0,2) rep(p,0,3)
        memo[i][j][k][l][t][p] = -INF;

    cin >> N >> M;
    rep(i,0,N) cin >> a[i];
    rep(i,0,M) cin >> b[i];

    // 1-indexed
    rep(i,0,N) suma[i+1] = (a[i] == -1 ? suma[i] : suma[i] + a[i]);
    rep(i,0,M) sumb[i+1] = (b[i] == -1 ? sumb[i] : sumb[i] + b[i]);
    cout << dfs(0, 0, 0, 0, 0, 0) << endl;
    return 0;
}

Submission Info

Submission Time
Task D - インビジブル
User tsutaj
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3069 Byte
Status MLE
Exec Time 224 ms
Memory 607872 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
MLE × 37
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 MLE 224 ms 607744 KB
00_sample_01 MLE 171 ms 607744 KB
00_sample_02 MLE 150 ms 607744 KB
30_random_small_000 MLE 150 ms 607744 KB
30_random_small_001 MLE 150 ms 607744 KB
30_random_small_002 MLE 149 ms 607744 KB
30_random_small_003 MLE 150 ms 607744 KB
30_random_small_004 MLE 150 ms 607744 KB
30_random_small_005 MLE 149 ms 607744 KB
30_random_small_006 MLE 150 ms 607744 KB
30_random_small_007 MLE 149 ms 607744 KB
30_random_small_008 MLE 149 ms 607744 KB
30_random_small_009 MLE 150 ms 607744 KB
31_random_skewed_000 MLE 150 ms 607744 KB
31_random_skewed_001 MLE 152 ms 607872 KB
31_random_skewed_002 MLE 150 ms 607744 KB
31_random_skewed_003 MLE 150 ms 607744 KB
31_random_skewed_004 MLE 150 ms 607744 KB
32_random_skewed_000 MLE 150 ms 607744 KB
32_random_skewed_001 MLE 150 ms 607744 KB
32_random_skewed_002 MLE 150 ms 607744 KB
32_random_skewed_003 MLE 150 ms 607744 KB
32_random_skewed_004 MLE 150 ms 607744 KB
33_random_frequent_invisible_000 MLE 150 ms 607744 KB
33_random_frequent_invisible_001 MLE 150 ms 607744 KB
33_random_frequent_invisible_002 MLE 150 ms 607872 KB
33_random_frequent_invisible_003 MLE 150 ms 607744 KB
33_random_frequent_invisible_004 MLE 150 ms 607744 KB
35_random_all_invisible_000 MLE 149 ms 607744 KB
36_random_all_same_score_000 MLE 157 ms 607744 KB
37_increasing_000 MLE 157 ms 607744 KB
38_decreasing_000 MLE 157 ms 607744 KB
40_random_max_000 MLE 151 ms 607744 KB
40_random_max_001 MLE 151 ms 607744 KB
40_random_max_002 MLE 151 ms 607744 KB
40_random_max_003 MLE 151 ms 607872 KB
40_random_max_004 MLE 151 ms 607744 KB