結果
問題 |
No.332 数列をプレゼントに
|
ユーザー |
![]() |
提出日時 | 2017-04-22 13:33:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,999 bytes |
コンパイル時間 | 1,547 ms |
コンパイル使用メモリ | 172,996 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 10:46:01 |
合計ジャッジ時間 | 5,127 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<b;i++) typedef long long ll; int N; ll X; int A[105]; //----------------------------------------------------------------------------------- int NB, NC, B[105], C[105]; void divide() { NB = N; rep(i, 0, N) B[i] = A[i]; sort(B, B + NB); while (0 < NB && NC < 20) { C[NC] = B[NB - 1]; NB--; NC++; } } //----------------------------------------------------------------------------------- int dp[105][201010]; pair<int,int> pre[105][201010]; void processB() { dp[0][0] = 1; pre[0][0] = { -1, 0 }; rep(i, 0, NB) rep(j, 0, 101010) if(dp[i][j]) { dp[i + 1][j] = 1; pre[i + 1][j] = { i, j }; dp[i + 1][j + B[i]] = 1; pre[i + 1][j + B[i]] = { i, j }; } } //----------------------------------------------------------------------------------- vector<int> processC() { rep(flag, 0, 1 << NC) { ll sm = 0; rep(j, 0, NC) if (flag & (1 << j)) sm += C[j]; ll d = X - sm; if (d < 0 || 101010 <= d) continue; if (!dp[NB][d]) continue; vector<int> res; rep(j, 0, NC) if (flag & (1 << j)) res.push_back(C[j]); pair<int, int> t = { NB, d }; while (0 <= t.first) { pair<int, int> tt = pre[t.first][t.second]; if (tt.second < t.second) res.push_back(t.second - tt.second); swap(t, tt); } return res; } return {}; } //----------------------------------------------------------------------------------- int main() { cin >> N >> X; rep(i, 0, N) cin >> A[i]; divide(); processB(); auto v = processC(); if (v.size() == 0) { printf("No\n"); return 0; } rep(i, 0, N) { bool ok = false; for (int &j : v) if (A[i] == j) { ok = true, j = -1; break; } if (ok) printf("o"); else printf("x"); } printf("\n"); }