oj.uz

Submission #491168

# Submission time Handle Problem Language Result Execution time Memory
491168 2021-11-30T16:41:58 Z tarche Knapsack (NOI18_knapsack) C++17
12 / 100
 2 ms 1740 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
    int S, N;
    cin >> S >> N;

    vector<int> value(N), weight(N), amount(N);
    for (int i = 0; i < N; i++)
        cin >> value[i] >> weight[i] >> amount[i];

    vector<vector<pair<int, int>>> dp(N, vector<pair<int, int>>(S + 1));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= S; j++) {
            int k = j + weight[i];
            if (dp[i][j].second < amount[i] && k <= S) {
                if (dp[i][k].first < dp[i][j].first + value[i]) {
                    dp[i][k].first = dp[i][j].first + value[i];
                    dp[i][k].second = dp[i][j].second + 1;
                }
            }

            if (i < N - 1 && dp[i + 1][j].first < dp[i][j].first) {
                dp[i + 1][j].first = dp[i][j].first;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= S; j++)
            ans = max(ans, dp[i][j].first);

    cout << ans << '\n';
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 1740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 1740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 2 ms 1740 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 2 ms 1740 KB Output isn't correct
7 Halted 0 ms 0 KB -