結果

問題 No.973 余興
ユーザー mkawa2mkawa2
提出日時 2020-01-17 23:04:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 924 bytes
コンパイル時間 1,864 ms
コンパイル使用メモリ 167,700 KB
実行使用メモリ 52,156 KB
最終ジャッジ日時 2024-06-25 23:58:01
合計ジャッジ時間 10,611 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 11 TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
const ll inf = 1e16;
const ll md = 1000000007;

int n,x;
int a[5005];
bool dp[5005][5005];
bool done[5005][5005];

bool win(int l,int r){
  if(done[l][r]) return dp[l][r];
  if(l+1==r) return false;
  bool res=false;
  ll s=0;
  for(int nl=l+1;nl<r;nl++){
    s+=a[nl-1];
    if(s>x) break;
    if(win(nl,r)==false){
      res=true;
      break;
    }
  }
  s=0;
  for(int nr=r-1;nr>l;nr--){
    if(res) break;
    s+=a[nr];
    if(s>x) break;
    if(win(l,nr)==false){
      res=true;
      break;
    }
  }
  done[l][r]=true;
  dp[l][r]=res;
  return res;
}

int main() {
  cin>>n>>x;
  rep(i,n) cin>>a[i];
  if(win(0,n)) puts("A");
  else puts("B");
  return 0;
}
0