結果
問題 | No.332 数列をプレゼントに |
ユーザー |
|
提出日時 | 2017-11-07 23:16:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,794 bytes |
コンパイル時間 | 2,001 ms |
コンパイル使用メモリ | 178,128 KB |
実行使用メモリ | 403,072 KB |
最終ジャッジ日時 | 2024-12-24 10:47:25 |
合計ジャッジ時間 | 5,603 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 41 MLE * 1 |
ソースコード
#include <bits/stdc++.h>#define show(x) cerr << #x << " = " << x << endlusing namespace std;using ll = long long;using pii = pair<int, int>;using vi = vector<int>;template <typename T>ostream& operator<<(ostream& os, const vector<T>& v){os << "sz=" << v.size() << "\n[";for (const auto& p : v) {os << p << ",";}os << "]\n";return os;}template <typename S, typename T>ostream& operator<<(ostream& os, const pair<S, T>& p){os << "(" << p.first << "," << p.second<< ")";return os;}constexpr ll MOD = 1e9 + 7;template <typename T>constexpr T INF = numeric_limits<T>::max() / 100;int main(){cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;ll X;cin >> X;constexpr ll LEVEL = 100000;using P = pair<ll, int>;vector<P> lower;vector<P> upper;ll lower_sum = 0;for (int i = 0; i < N; i++) {ll v;cin >> v;lower_sum += ((v >= LEVEL) ? 0 : v);((v >= LEVEL) ? upper : lower).push_back(make_pair(v, i));}const int upper_size = upper.size();const int maximum = 1 << upper_size;vector<ll> upper_sum(maximum, 0);for (int i = 0; i < maximum; i++) {for (int j = 0; j < upper_size; j++) {if (i & (1 << j)) {upper_sum[i] += upper[j].first;}if (upper_sum[i] > X) {upper_sum[i] = -1;}}}const int lower_size = lower.size();vector<vector<int>> dp(lower_size + 1, vector<int>(lower_sum + 1, -2));dp[0][0] = -1;for (int i = 0; i < lower_size; i++) {for (int j = 0; j <= lower_sum; j++) {if (dp[i][j] != -2) {dp[i + 1][j] = max(dp[i + 1][j], -1);dp[i + 1][j + lower[i].first] = i;}}}for (int i = 0; i < maximum; i++) {if (X < upper_sum[i] or upper_sum[i] < 0) {continue;}ll rest = X - upper_sum[i];if (rest > lower_sum) {continue;}if (dp[lower_size][rest] != -2) {vector<bool> use(N, false);for (int j = 0; j < upper_size; j++) {if (i & (1 << j)) {use[upper[j].second] = true;}}for (int j = lower_size; j >= 1; j--) {if (dp[j][rest] != -1) {use[lower[dp[j][rest]].second] = true;rest -= lower[dp[j][rest]].first;}}for (int j = 0; j < N; j++) {cout << (use[j] ? 'o' : 'x');}cout << "\n";return 0;}}cout << "No" << endl;return 0;}