結果
問題 | No.868 ハイパー部分和問題 |
ユーザー |
|
提出日時 | 2019-08-16 22:48:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,124 bytes |
コンパイル時間 | 936 ms |
コンパイル使用メモリ | 102,924 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 21:34:50 |
合計ジャッジ時間 | 17,839 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 WA * 1 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>#include <limits>static const int MOD = 1000000009;using ll = long long;using u32 = uint32_t;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;template <class T, class U>vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }template<class... Ts, class U>auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }template<ll M = 1000000007>struct modint{ll val;modint(): val(0){}template<typename T>explicit modint(T t){val = t%M; if(val < 0) val += M;}modint pow(ll k){modint res(1), x(val);while(k){if(k&1) res *= x;x *= x;k >>= 1;}return res;}template<typename T>modint& operator=(T a){ val = a%M; if(val < 0) val += M; return *this; }modint inv() {return pow(M-2);}modint& operator+=(modint a){ val += a.val; if(val >= M) val -= M; return *this;}modint& operator-=(modint a){ val += M-a.val; if(val >= M) val -= M; return *this;}modint& operator*=(modint a){ val = 1LL*val*a.val%M; return *this;}modint& operator/=(modint a){ return (*this) *= a.inv();}modint operator+(modint a) const {return modint(val) +=a;}modint operator-(modint a) const {return modint(val) -=a;}modint operator*(modint a) const {return modint(val) *=a;}modint operator/(modint a) const {return modint(val) /=a;}modint operator-(){ return modint(-val);}bool operator==(const modint a) const {return val == a.val;}bool operator!=(const modint a) const {return val != a.val;}bool operator<(const modint a) const {return val < a.val;}};using mint = modint<MOD>;int main() {int n, k;cin >> n >> k;vector<int> v(n);for (auto &&i : v) scanf("%d", &i);auto dp = make_v(2, k+1, mint(0));dp[0][0] = mint(1);for (int i = 1; i <= n; ++i) {int now = i&1, prv = now^1;for (int j = 0; j <= k; ++j) {dp[now][j] = dp[prv][j];if(j >= v[i-1]) dp[now][j] += dp[prv][j-v[i-1]];}}auto DP = dp[n%2];int q;cin >> q;for (int i = 0; i < q; ++i) {int x, u; scanf("%d %d", &x, &u);vector<mint> newdp(DP); x--;if(v[x] == 0){for (int j = 0; j <= k; ++j) {newdp[j] = DP[j] * mint(500000005);}}else {for (int j = v[x]; j <= k; ++j) {newdp[j] -= newdp[j-v[x]];}}for (int j = 0; j <= k; ++j) {DP[j] = newdp[j];if(j >= u) DP[j] += newdp[j-u];}v[x] = u;printf("%d\n", DP[k] != mint(0));}return 0;}