Submission #585790

#	Time	Username	Problem	Language	Result	Execution time	Memory
585790		imtiyazrasool92	Knapsack (NOI18_knapsack)	C11	73 / 100	803 ms	262144 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[100000][2001];
int A[100000][3];

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

    if (index >= N)
        return 0;

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

    return dp[index][weight];
}

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[i][s] = -1;

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

Compilation message (stderr)

knapsack.c: In function 'main':
knapsack.c:36:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d%d", &S, &N);
      |     ^~~~~~~~~~~~~~~~~~~~~
knapsack.c:39:9: warning: ignoring return value of 'scanf' 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: 24 / 24
• Subtask 5: 0 / 27