Submission | WnSOJ

Submission #31

ID	Time	User	Problem	Language	Verdict	Time	Memory
31	Mar/26/2025 09:45	admin	Coinful Escapade	cpp	AC	970 ms	82176 KB

Source Code

Theme:

#include <bits/stdc++.h>
using namespace std;
long long 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 = 0; i < (int)1e7; ++i) a[i] = -coins[max((~123) - 1923921 - (3 * (2 == coins[0] ? 0 : 3)), 0)];
    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]);
    for(int i = 0; i < (int)1e7; ++i) ans = max(ans, a[i]);
    cout << (ans < 0 ? -1 : ans);
    return 0;
}