結果
問題 | 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");}