Submission #37183627

Source Code Expand

#include <bits/stdc++.h>

typedef  long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
using namespace std;
int main() {
    int N, D, K;
    cin >> N >> K >> D;
    vector<ll> A(N+1);
    for (int i = 0; i < N; i++) {
        cin >> A[i+1];
    }
    vector<vector<vector<ll>>> dp(101, vector<vector<ll>>(101, vector<ll>(101)));
    dp[0][0][0] = 0;
    for (int n = 0; n < 101 ; n++) {
        for (int k = 0; k < 101; k++) {
            for (int d = 0; d < 101;d++) {
                dp[n][k][d] = -1;
            }
        }
    }
    for (int i = 1; i <= D; i++) {
        if (A[1] % D == i) {
            dp[1][1][i] = max(dp[1][1][i],A[1]);
        }
    }
    
    for (int n = 1; n < N; n++) {
        for (int k = 1; k < n; k++) {
            for (int d = 1; d <= D;d++) {
                ll a = A[n + 1] % D;
                if (dp[n][k][(d - a + D) % D]  == -1) {
                    dp[n + 1][k + 1][d] = dp[n][k + 1][d];
                }
                dp[n + 1][k + 1][d] = max(dp[n][k][(d - a + D) % D] + A[n+1], dp[n][k + 1][d]);
            }
        }
    }
    
    cout << dp[N][K][0] << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Max Multiple
User amaoto
Language C++ (GCC 9.2.1)
Score 0
Code Size 1205 Byte
Status WA
Exec Time 27 ms
Memory 11664 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 1
WA × 1
AC × 10
WA × 19
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_srnd_00.txt, 01_srnd_01.txt, 01_srnd_02.txt, 01_srnd_03.txt, 01_srnd_04.txt, 01_srnd_05.txt, 01_srnd_06.txt, 01_srnd_07.txt, 02_rnd_00.txt, 02_rnd_01.txt, 02_rnd_02.txt, 02_rnd_03.txt, 02_rnd_04.txt, 02_rnd_05.txt, 02_rnd_06.txt, 02_rnd_07.txt, 03_max_00.txt, 03_max_01.txt, 03_max_02.txt, 04_obvious_00.txt, 04_obvious_01.txt, 04_obvious_02.txt, 04_obvious_03.txt, 05_hand_00.txt, 05_hand_01.txt, 05_hand_02.txt, 05_hand_03.txt
Case Name Status Exec Time Memory
00_sample_00.txt WA 14 ms 11664 KiB
00_sample_01.txt AC 15 ms 11656 KiB
01_srnd_00.txt AC 13 ms 11488 KiB
01_srnd_01.txt AC 13 ms 11544 KiB
01_srnd_02.txt AC 13 ms 11460 KiB
01_srnd_03.txt AC 12 ms 11596 KiB
01_srnd_04.txt AC 17 ms 11656 KiB
01_srnd_05.txt AC 12 ms 11464 KiB
01_srnd_06.txt WA 12 ms 11464 KiB
01_srnd_07.txt AC 14 ms 11596 KiB
02_rnd_00.txt WA 22 ms 11540 KiB
02_rnd_01.txt WA 22 ms 11544 KiB
02_rnd_02.txt WA 18 ms 11472 KiB
02_rnd_03.txt WA 20 ms 11664 KiB
02_rnd_04.txt WA 15 ms 11484 KiB
02_rnd_05.txt WA 19 ms 11464 KiB
02_rnd_06.txt WA 14 ms 11604 KiB
02_rnd_07.txt WA 22 ms 11652 KiB
03_max_00.txt WA 27 ms 11540 KiB
03_max_01.txt AC 25 ms 11540 KiB
03_max_02.txt WA 21 ms 11536 KiB
04_obvious_00.txt WA 20 ms 11460 KiB
04_obvious_01.txt WA 14 ms 11588 KiB
04_obvious_02.txt WA 12 ms 11464 KiB
04_obvious_03.txt WA 14 ms 11464 KiB
05_hand_00.txt WA 27 ms 11548 KiB
05_hand_01.txt WA 18 ms 11460 KiB
05_hand_02.txt WA 21 ms 11548 KiB
05_hand_03.txt AC 23 ms 11464 KiB