結果
問題 | No.332 数列をプレゼントに |
ユーザー |
![]() |
提出日時 | 2015-12-25 20:47:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 575 ms / 2,000 ms |
コード長 | 2,703 bytes |
コンパイル時間 | 1,898 ms |
コンパイル使用メモリ | 186,536 KB |
実行使用メモリ | 85,376 KB |
最終ジャッジ日時 | 2024-12-24 07:36:53 |
合計ジャッジ時間 | 9,733 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef __uint128_t ll; typedef vector<int> vi; typedef vector<ll> vl; typedef complex<double> P; typedef pair<int,int> pii; #define REP(i,n) for(ll i=0;i<n;++i) #define REPR(i,n) for(ll i=1;i<n;++i) #define FOR(i,a,b) for(ll i=a;i<b;++i) #define DEBUG(x) cout<<#x<<": "<<x<<endl #define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl #define ALL(a) (a).begin(),(a).end() #define MOD (ll)(1e9+7) #define ADD(a,b) a=((a)+(b))%MOD #define FIX(a) ((a)%MOD+MOD)%MOD ostream& operator<<(ostream& s,ll value){ string out = ""; if(value==0){ out = "0"; }else{ while(value){ out = (char)(value%10+'0') + out; value /= 10; } } s << out; return s; } istream& operator>>(istream& s,ll& value){ string in = ""; s >> in; if(in.size()>13){ value = 1e14; return s; } value = 0; REP(i,in.size()){ value *= 10; value += in[i]-'0'; } return s; } int main(){ ll n,x; cin>>n>>x; vl a(n); REP(i,n)cin>>a[i]; if(x==1e14){ return(a[n+114514]); } // 先頭20個を別扱いにする解法 vl b = a; sort(ALL(b),greater<ll>()); vl c,d; ll dsz = min<int>(20,n); ll csz = n-dsz; REP(i,dsz)d.push_back(b[i]); FOR(i,dsz,n)c.push_back(b[i]); // ナップサック ll cmax = 0; REP(i,csz)cmax += c[i]; cmax = min(cmax,x); vector< vector<bool> > dp(csz+1,vector<bool>(cmax+1,false)); vector< vector<bool> > pred(csz+1,vector<bool>(cmax+1,false)); dp[0][0] = true; REP(i,csz){ ll cost = c[i]; REP(p,cmax+1){ if(!dp[i][p])continue; dp[i+1][p] = true; pred[i+1][p] = false; if(p+cost<=cmax){ dp[i+1][p+cost] = true; pred[i+1][p+cost] = true; } } } // 大きい値の全探索 map<ll,ll> XS; REP(mask,1<<dsz){ ll s = 0; REP(i,dsz) if(mask>>i&1) s+=d[i]; if(s>x)continue; XS[s] = mask; } // 合体 ll ansid = -1; REP(i,cmax+1){ if(dp[csz][i]&&XS.count(x-i)){ ansid = i; break; } } if(ansid==-1){ cout << "No" << endl; return 0; } // 復元 multiset<ll> result; // ここに使う値をぶっこんでいく // dp,predから ll cst = ansid; REP(_i,csz){ ll i = csz-_i; if(pred[i][cst]){ result.insert(c[i-1]); cst -= c[i-1]; } } assert(cst==0); // 全探索のmaskから ll mask = XS[x-ansid]; REP(i,dsz){ if(mask>>i&1)result.insert(d[i]); } // 出力 multiset<ll>::iterator iter; REP(i,n){ iter = result.find(a[i]); if(iter!=result.end()){ cout<<"o"; result.erase(iter); }else{ cout<<"x"; } } cout<<endl; return 0; }