結果

問題 No.1515 Making Many Multiples
コンテスト
ユーザー nok0
提出日時 2021-04-30 10:41:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 655 bytes
コンパイル時間 3,190 ms
コンパイル使用メモリ 204,040 KB
最終ジャッジ日時 2025-01-21 02:21:53
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

void chmax(int& x, const int y) {
	x = max(x, y);
}

int n, k, x, y, res;
int main() {
	cin >> n >> k >> x >> y;
	x %= k, y %= k;
	vector a(n, 0);
	for(auto& v : a) cin >> v, v %= k;
	map<pair<int, int>, int> dp;

	dp[{x, y}] = 0;
	for(const auto& v : a) {
		map<pair<int, int>, int> ndp;
		for(const auto& [key, val] : dp) {
			const auto [z, w] = key;
			int nxt = val + (v + z + w == 0 or v + z + w == k or v + z + w == 2 * k);
			chmax(ndp[{v, w}], nxt);
			chmax(ndp[{v, z}], nxt);
			chmax(ndp[{z, w}], nxt);
		}
		dp = ndp;
	}
	for(const auto& [key, val] : dp) chmax(res, val);
	cout << res << '\n';
}
0