結果

問題 No.332 数列をプレゼントに
ユーザー Pachicobue
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0