結果
| 問題 | No.332 数列をプレゼントに |
| ユーザー |
 sigma425
|
| 提出日時 | 2015-12-25 00:34:28 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 1,136 bytes |
| コンパイル時間 | 2,104 ms |
| コンパイル使用メモリ | 170,096 KB |
| 実行使用メモリ | 305,196 KB |
| 最終ジャッジ日時 | 2023-10-19 03:06:05 |
| 合計ジャッジ時間 | 5,991 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
7,736 KB |
| testcase_01 | AC | 2 ms
7,740 KB |
| testcase_02 | AC | 2 ms
5,688 KB |
| testcase_03 | AC | 2 ms
5,692 KB |
| testcase_04 | AC | 2 ms
4,348 KB |
| testcase_05 | AC | 13 ms
52,828 KB |
| testcase_06 | AC | 15 ms
65,116 KB |
| testcase_07 | AC | 21 ms
87,744 KB |
| testcase_08 | AC | 17 ms
67,196 KB |
| testcase_09 | AC | 3 ms
9,804 KB |
| testcase_10 | AC | 24 ms
15,936 KB |
| testcase_11 | AC | 13 ms
50,780 KB |
| testcase_12 | AC | 22 ms
91,740 KB |
| testcase_13 | AC | 17 ms
71,244 KB |
| testcase_14 | AC | 9 ms
36,476 KB |
| testcase_15 | AC | 20 ms
85,564 KB |
| testcase_16 | AC | 22 ms
76,348 KB |
| testcase_17 | AC | 20 ms
87,868 KB |
| testcase_18 | MLE | - |
| 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 | -- | - |
ソースコード
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
int N;
ll X,a[100];
vector<int> ls,ss; //large,small
typedef pair<ll,int> P;
set<P> st;
bool dp[101][1000001];
int main(){
cin>>N>>X;
rep(i,N) cin>>a[i];
rep(i,N){
if(a[i]>=10000) ls.pb(i);
else ss.pb(i);
}
int K=ls.size();
rep(i,1<<K){
ll S=0;
rep(j,K) if((i>>j)&1) S+=a[ls[j]];
st.insert(P(S,i));
}
int B=ss.size();
int S=0;
dp[0][0]=1;
rep(i,B){
rep(j,S+1){
if(dp[i][j]) dp[i+1][j+a[ss[i]]]=1,dp[i+1][j]=1;
}
S+=a[ss[i]];
}
rep(j,S+1) if(dp[B][j]){
auto it=st.lower_bound(P(X-j,0));
if(it==st.end()||it->fs!=X-j) continue;
string ans(N,'x');
int s=j;
for(int i=B-1;i>=0;i--){
if(!dp[i][s]) s-=a[ss[i]],ans[ss[i]]='o';
}
int id=it->sc;
rep(i,K) if((id>>i)&1) ans[ls[i]]='o';
cout<<ans<<endl;
return 0;
}
puts("No");
}