CSP-S复赛冲刺课程模拟卷(四)T4

2026-10-04 16:19:59

发布于：广东

24阅读

0回复

0点赞

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
	freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    ll n,k,d;
    cin>>n>>k>>d;
    vector<ll> a(n);
    for(ll i=0;i<n;i++)cin>>a[i];
    vector<vector<ll>>dp(k+1,vector<ll>(d,-1));
    dp[0][0]=0;
    for(ll i=0;i<n;i++){
        ll v=a[i];
        for(ll j=k-1;j>=0;j--){
            for(ll r=0;r<d;r++){
                if(dp[j][r]==-1)continue;
                ll nn=(r+v)%d;
                ll m=dp[j][r]+v;
                if(m>dp[j+1][nn])dp[j+1][nn]=m;
            }
        }
    }
    if(dp[k][0]==-1)cout<<-1;
	else cout<<dp[k][0];
}