Submission #630353

#	Time	Username	Problem	Language	Result	Execution time	Memory
630353		Galaxy	Knapsack (NOI18_knapsack)	C++14	73 / 100	1075 ms	2652 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20, M = 2010;
const int mod = 1e9 + 7;
#define x first
#define y second
typedef long long ll;
typedef pair<double, double> PDD;
int s, n, dp[M];
struct NODE{
    int v, w, k;
}node[N];

int main(){
//    freopen("123.in", "r", stdin);
    scanf("%d%d", &s, &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &node[i].v, &node[i].w, &node[i].k);
    }
    for(int i = 1; i <= n; i++){
        int v = node[i].v, w = node[i].w, k = node[i].k;
        if(k == 1){
            for(int j = s; j >= w; j--){
                dp[j] = max(dp[j], dp[j - w] + v);
            }
        }
        else if(k >= (s + w - 1) / w){
            for(int j = w; j <= s; j++){
                dp[j] = max(dp[j], dp[j - w] + v);
            }
        }
        else{
            vector<int> qwe;
            for(int u = 1; u <=k; u <<= 1){
                qwe.push_back(u);
                k -= u;
            }
            if(k) qwe.push_back(k);
            for(auto k:qwe){
                for(int j = s; j >= k * w ;j--){
                    dp[j] = max(dp[j], dp[j - k * w] + k * v);
                }
            }
        }
    }
    printf("%d\n", dp[s]);
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d", &s, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%d%d", &node[i].v, &node[i].w, &node[i].k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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