Submission #585797

#	Time	Username	Problem	Language	Result	Execution time	Memory
585797		imtiyazrasool92	Knapsack (NOI18_knapsack)	C++17	49 / 100	1089 ms	10572 KiB

knapsack

#include<stdio.h>

int min(int A, int B) {
    return A > B ? B : A;
}

int max(int A, int B) {
    return A < B ? B : A;
}

int S, N;
int dp[2001][100000];
int A[100000][3];

int dfs(int index, int weight) {
    if (weight == 0)
        return 0;

    if (index >= N)
        return 0;

    if (dp[weight][index] == -1) {
        dp[weight][index] = 0;
        for (int i = 0; i <= min(weight / A[index][1], A[index][2]); i++) {
            if (weight - (i * A[index][1]) >= 0)
                dp[weight][index] = max(dp[weight][index], dfs(index + 1, weight - (i * A[index][1])) + A[index][0] * i);
            else
                break;
        }
    }

    return dp[weight][index];
}

int main() {
    scanf("%d%d", &S, &N);

    for (int i = 0; i < N; i++) {
        scanf("%d%d%d", &A[i][0], &A[i][1], &A[i][2]);
        if (A[i][1] > S) {
            N--;
            i--;
        } else if (A[i][1] == 0) {
            N--;
            i--;
        }
    }

    for (int i = 0; i < N; i++)
        for (int s = 0; s <= S; s++)
            dp[s][i] = -1;

    printf("%d", dfs(0, S));
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d%d", &S, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d%d%d", &A[i][0], &A[i][1], &A[i][2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27