C 解法, 执行用时: 5ms, 内存消耗: 328KB, 提交时间: 2022-07-17

#include <stdio.h>
 
long long max(long long a, long long b) {
    return a > b ? a : b;
}
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
     
    long long a[n];
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
     
    long long dp[k];
    long long ndp[k];
    dp[0] = 0;
    for (int i = 1; i < k; i++) {
        dp[i] = -100000000000009;
    }
    long long v, mod;
    for (int i = 0; i < n; i++) {
        v = a[i];
        mod = v % k;
         
        if (mod == 0) {
            for (int j = 0; j < k; j++) {
                dp[j] += v;
            }
        } else {
            for (int j = 0; j < k; j++) {
                ndp[j] = max(dp[j], ((j >= mod) ? dp[j-mod] : dp[j+k-mod]) + v);
            }
            for (int j = 0; j < k; j++) {
                dp[j] = ndp[j];
            }
        }
    }
     
    if (dp[0] > 0) {
        printf("%lld", dp[0]);
    } else {
        printf("-1");
    }
     
    return 0;
}

C 解法, 执行用时: 5ms, 内存消耗: 344KB, 提交时间: 2022-06-21

#include <stdio.h>

long long max(long long a, long long b) {
    return a > b ? a : b;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    long long a[n];
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    
    long long dp[k];
    long long ndp[k];
    dp[0] = 0;
    for (int i = 1; i < k; i++) {
        dp[i] = -100000000000009;
    }
    long long v, mod;
    for (int i = 0; i < n; i++) {
        v = a[i];
        mod = v % k;
        
        if (mod == 0) {
            for (int j = 0; j < k; j++) {
                dp[j] += v;
            }
        } else {
            for (int j = 0; j < k; j++) {
                ndp[j] = max(dp[j], ((j >= mod) ? dp[j-mod] : dp[j+k-mod]) + v);
            }
            for (int j = 0; j < k; j++) {
                dp[j] = ndp[j];
            }
        }
    }
    
    if (dp[0] > 0) {
        printf("%lld", dp[0]);
    } else {
        printf("-1");
    }
    
    return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 416KB, 提交时间: 2021-11-06

#include <bits/stdc++.h>
using namespace std;
int n,k;long long a[1001];
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)scanf("%d",a+i);
    long long dp[2][1001]={},di;
    int off[2001];for(int i=0;i<k;i++){off[i]=i;off[i+k]=i;};
    for(int i=0;i<n;i++){
        di=i%2;long long (&pre)[1001]=dp[1-di],(&cur)[1001]=dp[di];
        int*offnow=off+a[i]%k;
        for(int j=0;j<k;j++){
            int index=offnow[j];
            cur[index]=pre[index];
            if(pre[j])
                cur[index]=max(cur[index],pre[j]+a[i]);
        }
        int ind=offnow[0];
        cur[ind]=max(cur[ind],a[i]);
    }
    di=(n-1)%2;long long (&pre)[1001]=dp[1-di],(&cur)[1001]=dp[di];
    if(cur[0]==0)printf("-1");
    else printf("%lld",cur[0]);
    return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 428KB, 提交时间: 2022-05-08

#include <bits/stdc++.h>
using namespace std;
int n, k;
long long a[1001];
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    long long d[2][1001] = {}, e;
    int f[2001];
    for (int i = 0; i < k; i++) {
        f[i] = i;
        f[i + k] = i;
    };
    for (int i = 0; i < n; i++) {
        e = i % 2;
        long long (&pre)[1001] = d[1 - e], (&cur)[1001] = d[e];
        int* off = f + a[i] % k;
        for (int j = 0; j < k; j++) {
            int x = off[j];
            cur[x] = pre[x];
            if (pre[j])
                cur[x] = max(cur[x], pre[j] + a[i]);
        }
        int ind = off[0];
        cur[ind] = max(cur[ind], a[i]);
    }
    e = (n - 1) % 2;
    long long (&pre)[1001] = d[1 - e], (&cur)[1001] = d[e];
    if (cur[0] == 0)
        printf("-1");
    else
        printf("%lld", cur[0]);
    return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 432KB, 提交时间: 2021-12-24

#include <bits/stdc++.h>
using namespace std;
int n,k;
long long a[1001];
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)scanf("%d",a+i);
    long long dp[2][1001]={},di;
    int off[2001];
    for(int i=0;i<k;i++){off[i]=i;off[i+k]=i;};//记录余数
    for(int i=0;i<n;i++){
        di=i%2;
        long long (&pre)[1001]=dp[1-di],(&cur)[1001]=dp[di];
        int* offnow = off + a[i] % k;
        for(int j=0;j<k;j++){
            int index=offnow[j];
            cur[index]=pre[index];
            if(pre[j])
                cur[index]=max(cur[index],pre[j]+a[i]);
        }
        int ind=offnow[0];
        cur[ind]=max(cur[ind],a[i]);
    }
    di=(n-1)%2;
    long long (&pre)[1001]=dp[1-di],(&cur)[1001]=dp[di];
    if(cur[0]==0)printf("-1");
    else printf("%lld",cur[0]);
    return 0;
}