結果
問題 |
No.332 数列をプレゼントに
|
ユーザー |
|
提出日時 | 2016-06-11 02:46:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 2,315 bytes |
コンパイル時間 | 848 ms |
コンパイル使用メモリ | 93,332 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-12-24 08:36:49 |
合計ジャッジ時間 | 3,479 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> #include <array> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define FOREACH(i, a) for(int i=0;i<a.size();++i) #define inf 0x3f3f3f3f #define CLEAR(a) a = decltype(a)() #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define pii pair<int ,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define pi 2*acos(0.0) #define INFILE() freopen("in.txt","r",stdin) #define OUTFILE() freopen("out.txt","w",stdout) #define ll long long #define ull unsigned long long #define eps 1e-14 int main(void) { //input ull lim = 1e5; ull N, X; cin >> N >> X; vector<ull> AO(N); vector<ull> AL; vector<ull> AU; REP(i, N) { cin >> AO[i]; if (AO[i] < lim) AL.push_back(AO[i]); else AU.push_back(AO[i]); } sort(ALL(AL)); int upper = -1; //GetSum of lower & index of upper.begin int sum_lower = 0; FOREACH(i, AL) { sum_lower += AL[i]; } //dp[value] = (prior value); vector<ull> dp(sum_lower+1); dp[0] = -1; REP(i, AL.size()) { RFOR(j, 0, sum_lower + 1) { if (j - AL[i] < dp.size()) if (dp[j] == 0 && dp[j - AL[i]] != 0) dp[j] = AL[i]; } } vector<ull> ansvalue; for (ull mask = 0; mask < (1 << AU.size()); ++mask) { ull sum = 0; REP(i, AU.size()) if (mask&(1 << i)) sum += AU[i]; int s = X - sum; if (s >= 0 && s < dp.size()) if (dp[s] != 0){ REP(i, AU.size()) if (mask&(1 << i)) ansvalue.push_back(AU[i]); // retrospective while (dp[s] != -1) { ansvalue.push_back(dp[s]); s = s - dp[s]; } break; } } if (ansvalue.size() == 0) cout << "No" << endl; else { for (auto &a : AO) { auto it = find(ALL(ansvalue), a); if (it != ansvalue.end()) { ansvalue.erase(it); cout << "o"; } else cout << "x"; } cout << endl; } return 0; }