結果
問題 | No.1515 Making Many Multiples |
ユーザー |
![]() |
提出日時 | 2021-05-02 16:07:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 278 ms / 2,000 ms |
コード長 | 1,053 bytes |
コンパイル時間 | 2,100 ms |
コンパイル使用メモリ | 206,028 KB |
最終ジャッジ日時 | 2025-01-21 05:56:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;void chmax(int& x, const int y) {x = max(x, y);}#define rep(i, x) for(int i = 0; i < (x); i++)using T = tuple<int, int, int>;int n, K, x, y, res;int main() {cin >> n >> K >> x >> y;x %= K, y %= K;vector a(n, 0);vector dp(vector(K, vector(K, -1)));vector dp2(vector(K, -1));for(auto& v : a) cin >> v, v %= K;dp[x][y] = 0;dp2[x] = dp2[y] = 0;rep(i, n) {queue<T> upd;rep(j, K) {for(int sum = 0; sum <= 2 * K; sum += K) {int k = sum - j - a[i];if(!(clamp(k, 0, K - 1) == k)) continue;auto& now = dp[j][k];if(now == -1) continue;upd.emplace(j, k, now + 1);upd.emplace(a[i], j, now + 1);upd.emplace(a[i], k, now + 1);}upd.emplace(j, a[i], dp2[j]);}while(!upd.empty()) {auto [j, k, val] = upd.front();upd.pop();chmax(dp[j][k], val);chmax(dp[k][j], val);chmax(dp2[j], val);chmax(dp2[k], val);}}rep(i, K) chmax(res, *max_element(dp[i].begin(), dp[i].end()));cout << res << '\n';return 0;}