結果
| 問題 | No.973 余興 |
| ユーザー |
 mugen_1337
|
| 提出日時 | 2021-04-13 15:25:10 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,855 bytes |
| コンパイル時間 | 2,264 ms |
| コンパイル使用メモリ | 213,388 KB |
| 実行使用メモリ | 141,056 KB |
| 最終ジャッジ日時 | 2024-06-29 20:16:03 |
| 合計ジャッジ時間 | 12,862 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 998244353
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
struct IOSetup{
IOSetup(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(12);
}
} iosetup;
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
for(T &x:v)is>>x;
return is;
}
vector<bitset<5001>> dp(5001);
set<int> st_l[5001],st_r[5001];
void solve(){
int n;ll x;cin>>n>>x;
vector<ll> v(n);
cin>>v;
vector<ll> s(n);
s[0]=v[0];
for(int i=1;i<n;i++) s[i]=s[i-1]+v[i];
rep(i,n) st_l[i].insert(i+1);
rep(i,n) st_r[i+1].insert(i);
for(int w=2;w<=n;w++){
for(int l=0;l+w<=n;l++){
int r=l+w;// [l,r)
bool win=false;
// left
{
ll offset=(l==0?0:s[l-1]);
int ri=lower_bound(begin(s),end(s),offset+x+1)-begin(s);
// can take [l,r)
auto ite=st_r[r].lower_bound(l+1);
if(ite!=end(st_r[r]) and *ite<=ri) win=true;
}
// right
{
int li=lower_bound(begin(s),end(s),s[r-1]-x+1)-begin(s);
// can take [li,r)
auto ite=st_l[l].lower_bound(li);
if(ite!=end(st_l[l]) and *ite<r) win=true;
}
dp[l][r]=win;
if(!win){
st_l[l].insert(r);
st_r[r].insert(l);
}
}
}
cout<<(dp[0][n]?"A":"B")<<endl;
}
void naive(){
int n;ll x;cin>>n>>x;
vector<ll> v(n);
cin>>v;
for(int w=2;w<=n;w++){
for(int l=0;l+w<=n;l++){
int r=l+w;// [l,r)
bool win=false;
// left
{
ll s=v[l];
for(int i=l+1;i<r and s<=x;i++){
if(!dp[i][r]) win=true;
s+=v[i];
}
}
// right
{
ll s=v[r-1];
for(int i=r-1;i>l and s<=x;i--){
if(!dp[l][i]) win=true;
s+=v[i-1];
}
}
dp[l][r]=win;
}
}
cout<<(dp[0][n]?"A":"B")<<endl;
}
signed main(){
// naive();
solve();
return 0;
}