Submission #27496390

Source Code Expand

#include<bits/stdc++.h>
using namespace std;


int main() {
    long long n, w;
    cin >> n >> w;
    long long wei[n], val[n];
    long long dp[200010][110];

    for (long long i = 0; i < n; i++){
        cin >> wei[i] >> val[i];
    }

    for (long long i = 0; i < 200010; i++){
        for (long long j = 0; j < 110; j++){
            dp[i][j] = 0;
        }
    }

    dp[wei[0]][0] = val[0];
    dp[wei[0]][1] = val[0];

    for (long long i = 1; i < n; i++){
        for (long long j = 0; j < w; j++){
            dp[j + wei[i]][i] = max(dp[j + wei[i]][i], max(dp[j + wei[i]][i], dp[j][i - 1] + val[i]));
            dp[j + wei[i]][i + 1] = dp[j + wei[i]][i];
            dp[j + wei[i] + 1][i] = max(dp[j + wei[i] + 1][i], dp[j + wei[i]][i]);
        }
    }

    cout << dp[w][n - 1] << endl;
}

Submission Info

Submission Time
Task D - Knapsack 1
User Yutchy591
Language C++ (GCC 9.2.1)
Score 0
Code Size 836 Byte
Status WA
Exec Time 214 ms
Memory 175416 KiB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 6
WA × 7
Set Name Test Cases
All 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09
Case Name Status Exec Time Memory
0_00 AC 109 ms 175408 KiB
0_01 AC 108 ms 175344 KiB
0_02 AC 107 ms 175352 KiB
1_00 AC 108 ms 175356 KiB
1_01 AC 172 ms 175316 KiB
1_02 WA 214 ms 175188 KiB
1_03 WA 206 ms 175348 KiB
1_04 WA 197 ms 175188 KiB
1_05 WA 189 ms 175408 KiB
1_06 WA 184 ms 175384 KiB
1_07 WA 177 ms 175208 KiB
1_08 WA 172 ms 175416 KiB
1_09 AC 170 ms 175248 KiB