結果
問題 |
No.332 数列をプレゼントに
|
ユーザー |
![]() |
提出日時 | 2016-03-16 19:41:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,605 bytes |
コンパイル時間 | 644 ms |
コンパイル使用メモリ | 61,600 KB |
実行使用メモリ | 53,572 KB |
最終ジャッジ日時 | 2024-10-01 08:47:22 |
合計ジャッジ時間 | 4,931 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 2 WA * 2 TLE * 1 -- * 37 |
ソースコード
#include <iostream> #include <cstring> #include <vector> using namespace std; int n; long long x; long long a[100]; bool z[100]; const int psize = 100; vector<int> p; int dp[psize][101][1100]; bool is_prime(int x) { for (int i = 2; i < x; i++) if (x % i == 0) return false; return true; } void init() { for (int i = 2; p.size() < psize; i++) { if (is_prime(i)) p.push_back(i); } } bool solve() { init(); 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 < psize; 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 < psize; 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 < psize; 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; }