Submission #1192491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192491		dprto	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	320 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 100, maxX = 1e5+1;

int N, X, h[maxN], s[maxN], k[maxN];
ll dp[maxX];

int main(){
    scanf("%d %d", &N, &X);
    for(int i = 0; i < N; i++)  scanf("%d", &h[i]);
    for(int i = 0; i < N; i++)  scanf("%d", &s[i]);
    for(int i = 0; i < N; i++)  scanf("%d", &k[i]);

    fill(dp+1, dp+X+1, -1);
    for(int i = 0; i < N; i++){
        for(int b = 1; k[i] > 0; b <<= 1){
            int amnt = min(b, k[i]);
            k[i] -= amnt;
            int price = amnt * h[i];
            int pages = amnt * s[i];
            for(int j = X; j >= price; j--){
                if(dp[j-price] != -1){
                    dp[j] = max(dp[j], dp[j-price] + pages);
                }
            }
        }
    }

    for(int i = 1; i <= X; i++)
        dp[i] = max(dp[i], dp[i-1]);
    printf("%lld\n", dp[X]);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d", &N, &X);
      |     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:11:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for(int i = 0; i < N; i++)  scanf("%d", &h[i]);
      |                                 ~~~~~^~~~~~~~~~~~~
knapsack.cpp:12:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for(int i = 0; i < N; i++)  scanf("%d", &s[i]);
      |                                 ~~~~~^~~~~~~~~~~~~
knapsack.cpp:13:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for(int i = 0; i < N; i++)  scanf("%d", &k[i]);
      |                                 ~~~~~^~~~~~~~~~~~~

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