WnSOJ
Home
Problems
Jobs
FAQ
API
Swagger UI
ReDoc
Login
Register
Submission #22
ID
Time
User
Problem
Language
Verdict
Time
Memory
22
Mar/26/2025 05:02
admin
Coinful Escapade
cpp
AC
642 ms
3840 KB
Source Code
Theme:
default
darcula
eclipse
Copy Code
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<long long> coins(n); for (int i = 0; i < n; i++) cin >> coins[i]; const long long MINF = -1e18; vector<long long> dp0(k, MINF), dp1(k, MINF); dp0[0] = 0; for (int i = 0; i < n; i++){ vector<long long> ndp0(k, MINF), ndp1(k, MINF); int add = coins[i] % k; for (int r = 0; r < k; r++){ if(dp0[r] != MINF){ ndp0[r] = max(ndp0[r], dp0[r]); int nr = (r + add) % k; ndp1[nr] = max(ndp1[nr], dp0[r] + coins[i]); } if(dp1[r] != MINF){ ndp0[r] = max(ndp0[r], dp1[r]); } } dp0 = ndp0; dp1 = ndp1; } long long ans = max(dp0[0], dp1[0]); cout << (ans < 0 ? -1 : ans); return 0; }
cpp