結果
問題 | No.2215 Slide Subset Sum |
ユーザー | shobonvip |
提出日時 | 2023-04-27 22:55:16 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,213 ms / 3,000 ms |
コード長 | 1,808 bytes |
コンパイル時間 | 2,469 ms |
コンパイル使用メモリ | 216,068 KB |
実行使用メモリ | 177,144 KB |
最終ジャッジ日時 | 2024-04-28 12:02:06 |
合計ジャッジ時間 | 57,455 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 394 ms
36,292 KB |
testcase_01 | AC | 2,120 ms
176,924 KB |
testcase_02 | AC | 2,197 ms
176,940 KB |
testcase_03 | AC | 2,187 ms
177,144 KB |
testcase_04 | AC | 2,202 ms
176,656 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 5 ms
5,376 KB |
testcase_17 | AC | 2,142 ms
171,980 KB |
testcase_18 | AC | 2,137 ms
172,588 KB |
testcase_19 | AC | 2,213 ms
176,856 KB |
testcase_20 | AC | 2,129 ms
171,744 KB |
testcase_21 | AC | 2,179 ms
175,568 KB |
testcase_22 | AC | 2,108 ms
171,592 KB |
testcase_23 | AC | 2,069 ms
168,960 KB |
testcase_24 | AC | 2,078 ms
168,960 KB |
testcase_25 | AC | 2,097 ms
169,728 KB |
testcase_26 | AC | 2,122 ms
171,572 KB |
testcase_27 | AC | 60 ms
9,088 KB |
testcase_28 | AC | 70 ms
9,216 KB |
testcase_29 | AC | 117 ms
14,592 KB |
testcase_30 | AC | 900 ms
77,508 KB |
testcase_31 | AC | 624 ms
57,472 KB |
testcase_32 | AC | 149 ms
17,536 KB |
testcase_33 | AC | 1,218 ms
103,056 KB |
testcase_34 | AC | 957 ms
82,120 KB |
testcase_35 | AC | 135 ms
15,176 KB |
testcase_36 | AC | 349 ms
34,816 KB |
testcase_37 | AC | 2,043 ms
168,064 KB |
testcase_38 | AC | 178 ms
14,940 KB |
testcase_39 | AC | 2,123 ms
176,920 KB |
testcase_40 | AC | 247 ms
23,920 KB |
testcase_41 | AC | 2 ms
5,376 KB |
testcase_42 | AC | 2,119 ms
171,748 KB |
testcase_43 | AC | 2,175 ms
176,760 KB |
testcase_44 | AC | 2,179 ms
176,888 KB |
testcase_45 | AC | 2,077 ms
169,940 KB |
testcase_46 | AC | 2,081 ms
169,888 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 998244353; typedef tuple<int,int,int> T; ll answer(vector<ll> &a, vector<ll> &b, int k){ ll ret = 0; for (int i=0; i<k; i++){ ret += a[i] * b[(k-i) % k]; ret %= mod; } return ret; } vector<ll> addone(vector<ll> &a, int x, int k){ vector<ll> ret = a; for (int i=0; i<k; i++){ ret[(i+x)%k] += a[i]; ret[(i+x)%k] %= mod; } return ret; } void calc(int l, int r, int mid, int k, vector<int> &a, vector<T> &q, vector<ll> &ans, vector<vector<ll>> &dp){ dp[mid] = vector<ll>(k); dp[mid][0] = 1; for (int i=mid-1; i>=l; i--){ dp[i] = addone(dp[i+1], a[i], k); } for (int i=mid+1; i<=r; i++){ dp[i] = addone(dp[i-1], a[i-1], k); } for (auto [ind, l, r]: q){ ans[ind] = (answer(dp[l], dp[r], k) - 1 + mod) % mod; } } void gogo(int l, int r, int k, vector<int> &a, vector<T> &q, vector<ll> &ans, vector<vector<ll>> &dp){ if (r-l <= 1){ for (auto [ind, l, r]: q){ if (a[l] == 0) ans[ind] = (ll)1; else ans[ind] = (ll)0; } return; } int mid = (l + r) / 2; vector<T> gocalc, lquery, rquery; for (auto [ind, l, r]: q){ if (mid <= l) rquery.push_back(make_tuple(ind, l, r)); else if (r <= mid) lquery.push_back(make_tuple(ind, l, r)); else gocalc.push_back(make_tuple(ind, l, r)); } calc(l, r, mid, k, a, gocalc, ans, dp); gogo(l, mid, k, a, lquery, ans, dp); gogo(mid, r, k, a, rquery, ans, dp); return; } int main(){ int n, m, k; cin >> n >> m >> k; vector<int> a(n); vector<vector<ll>> dp(n+1, vector<ll>(k)); for (int i=0; i<n; i++){ cin >> a[i]; } int qnum = n-m+1; vector<T> q(qnum); vector<ll> ans(qnum); for (int i=0; i<qnum; i++){ q[i] = make_tuple(i, i, i+m); } gogo(0, n, k, a, q, ans, dp); for (int i=0; i<qnum; i++){ cout << ans[i] << "\n"; } }