結果
問題 | No.868 ハイパー部分和問題 |
ユーザー |
|
提出日時 | 2019-08-17 10:18:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,098 ms / 7,000 ms |
コード長 | 957 bytes |
コンパイル時間 | 1,633 ms |
コンパイル使用メモリ | 171,128 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 18:58:54 |
合計ジャッジ時間 | 14,204 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = long long;#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)#define all(x) x.begin(),x.end()#define let auto constint main() {i64 N, K;cin >> N >> K;vector<i64> A(N + 1);rep(i,1,N + 1) cin >> A[i];i64 mod = (1ll << 55) + 55;vector<i64> dp(K + 1, 0);dp[0] = 1;auto fix = [mod](i64 m) {if(m < 0) return m + mod;if(m >= mod) return m - mod;return m;};rep(i,1,N + 1) {if(A[i] != 0) {for(int j = K; j >= A[i]; j--) {dp[j] = fix(dp[j] + dp[j - A[i]]);}}}i64 Q;cin >> Q;rep(q, 0, Q) {i64 x, v;cin >> x >> v;if(A[x] != 0) {for(int j = A[x]; j <= K; j++) {dp[j] = fix(dp[j] - dp[j - A[x]]);}}A[x] = v;if(A[x] != 0) {for(int j = K; j >= A[x]; j--) {dp[j] = fix(dp[j] + dp[j - A[x]]);}}cout << (dp[K] != 0) << endl;}}