結果
問題 |
No.332 数列をプレゼントに
|
ユーザー |
|
提出日時 | 2015-12-26 03:14:11 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 2,163 bytes |
コンパイル時間 | 957 ms |
コンパイル使用メモリ | 93,252 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 07:38:16 |
合計ジャッジ時間 | 3,475 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> #include <functional> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <sstream> #include <string> #define repd(i,a,b) for (int i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define var auto #define mod 1000000007 #define inf 2147483647 #define mp make_pair #define pb push_back typedef long long ll; using namespace std; template <typename T> inline void output(T a, int p) { if(p){ cout << fixed << setprecision(p) << a << "\n"; } else{ cout << a << "\n"; } } // end of template int main() { cin.tie(0); ios::sync_with_stdio(0); // source code int N; // N <= 100 ll X; cin >> N >> X; vector<pair<ll, int>> A(N); rep(i, N){ cin >> A[i].first; A[i].second = i; } string ret = ""; rep(i, N){ ret += 'x'; } sort(A.begin(), A.end()); ll sum = 0; int cnt = 0; while (cnt < N) { if (sum + A[cnt].first > 200000) { break; } sum += A[cnt].first; cnt++; } vector<ll> dp(sum + 1, -1); dp[0] = 0; rep(i, cnt){ for (int j = (int)sum; j >= 0; j--) { if (dp[j] >= 0 && dp[j + A[i].first] == -1) { dp[j + A[i].first] = i; } } } bool exist = false; rep(i, 1 << (N - cnt)){ ll tmp = 0; rep(j, N - cnt){ if (i & (1 << j)) tmp += A[cnt + j].first; } if (X - tmp < 0 || X - tmp > sum) continue; if (dp[X - tmp] >= 0) { rep(j, N - cnt){ if (i & (1 << j)) ret[A[cnt + j].second] = 'o'; } ll left = X - tmp; while (left) { ret[A[dp[left]].second] = 'o'; left -= A[dp[left]].first; } exist = true; break; } } if (exist) { cout << ret << endl; } else{ output("No", 0); } return 0; }