結果
問題 |
No.332 数列をプレゼントに
|
ユーザー |
![]() |
提出日時 | 2016-03-16 19:27:52 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,334 bytes |
コンパイル時間 | 672 ms |
コンパイル使用メモリ | 57,636 KB |
実行使用メモリ | 13,636 KB |
最終ジャッジ日時 | 2024-10-01 20:19:22 |
合計ジャッジ時間 | 7,374 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 8 WA * 21 TLE * 1 -- * 12 |
ソースコード
#include <iostream> #include <cstring> using namespace std; int n; long long x; long long a[100]; bool z[100]; int p[] = {1009, 1013, 1019}; int dp[3][101][1100]; bool solve() { long long sum = 0; for (int i = 0; i < n; i++) sum += a[i]; if (x > sum) return false; memset(dp, -1, sizeof(dp)); for (int k = 0; k < 3; k++) { dp[k][0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < p[k]; j++) { if (dp[k][i][j] == -1) continue; dp[k][i+1][j] = dp[k][i][j]; dp[k][i+1][(j+a[i]) % p[k]] = i; } } } bool r = true; for (int k = 0; k < 3; k++) r &= dp[k][n][x % p[k]] != -1; if (r) { while (x > 0) { for (int i = 0; i < n; i++) { bool ck = true; for (int k = 0; k < 3; k++) { if (dp[k][i][(x-a[i]) % p[k]] == -1) ck = false; } if (ck) { x -= a[i]; z[i] = true; break; } } } } return r; } int main(int argc, char *argv[]) { cin >> n >> x; for (int i = 0; i < n; i++) cin >> a[i]; if (solve()) { string ret; for (int i = 0; i < n; i++) { if (z[i]) ret += 'o'; else ret += 'x'; } cout << ret << endl; } else { cout << "No" << endl; } return 0; }