Submission | WnSOJ

Submission #29

ID	Time	User	Problem	Language	Verdict	Time	Memory
29	Mar/26/2025 09:42	admin	Coinful Escapade	cpp	AC	708 ms	4608 KB

Source Code

Theme:

#include <bits/stdc++.h>
using namespace std;
int a[(int)1e7];
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], a[i] = coins[i];
    for(int i = (int)1e7 - (n - 1); i < (int)1e7; ++i) a[i] = -coins[(int)1e7 - i];
    const long long MINF = -1e18;
    vector<long long> dp0(k, MINF), dp1(k, MINF);
    dp0[0] = 0;
    vector<long long> ndp0(k, MINF), ndp1(k, MINF);
    for (int i = 0; i < n; i++){
        ndp0.assign(k, MINF);
        ndp1.assign(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]);
            }
        }
        for(int r = 0; r < k; ++r) dp0[r] = ndp0[r], dp1[r] = ndp1[r];
    }
    long long ans = max(dp0[0], dp1[0]);
    cout << (ans < 0 ? -1 : ans);
    return 0;
}