結果

問題 No.973 余興
コンテスト
ユーザー どらら
提出日時 2020-01-22 00:09:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,025 ms / 4,000 ms
コード長 1,681 bytes
コンパイル時間 1,652 ms
コンパイル使用メモリ 171,716 KB
実行使用メモリ 206,704 KB
最終ジャッジ日時 2024-07-06 13:12:10
合計ジャッジ時間 31,113 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

int dp[5005][5005];
int dp1[5005][5005];
int dp2[5005][5005];

int main(){
  int N, X;
  cin >> N >> X;
  vector<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }

  vector<int> s_lhs(N), s_rhs(N);
  rep(i,N){
    {
      ll sum = 0;
      int ii = i;
      for(;ii<N; ii++){
        if(sum + v[ii] > X) break;
        sum += v[ii];
      }
      s_lhs[i] = min(N-1, ii);
    }
    {
      ll sum = 0;
      int ii = i;
      for(;ii>=0; ii--){
        if(sum + v[ii] > X) break;
        sum += v[ii];
      }
      s_rhs[i] = max(0, ii);
    }
  }

  for(int x=0; x<N; x++){
    for(int y=x; y<N; y++){
      int i = y-x;
      int j = y;

      if(i==j){
        dp[i][j] = 0;
        dp1[i][j] = 1;
        dp2[i][j] = 1;
      }else{
        // 左方向の範囲s_rhs[j]--(j-1) & 下方向の範囲(i+1)--s_lhs[i]
        int cnt1 = dp1[i][j-1] - (s_rhs[j]-1>=0?dp1[i][s_rhs[j]-1]:0);
        int cnt2 = dp2[i+1][j] - (s_lhs[i]+1<N?dp2[s_lhs[i]+1][j]:0);
        
        if(cnt1 > 0 || cnt2 > 0){//負けがある＝勝てる
          dp[i][j] = 1;
          dp1[i][j] = dp1[i][j-1];
          dp2[i][j] = dp2[i+1][j];
        }else{
          dp[i][j] = 0;
          dp1[i][j] = 1 + dp1[i][j-1];
          dp2[i][j] = 1 + dp2[i+1][j];
        }
      }
    }
  }

  if(dp[0][N-1] == 1) cout << "A" << endl;
  else cout << "B" << endl;
  
  return 0;
}
0