Submission #789525

#	Time	Username	Problem	Language	Result	Execution time	Memory
789525		codergirl	Knapsack (NOI18_knapsack)	C++14	37 / 100	2 ms	340 KiB

knapsack

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>

int main() {
    std::vector<long> v, w; int s, n, x, y, z; std::scanf("%d %d", &s, &n); long counter = 0, t = 0;
    
    for (int i=0; i < n; i++) {
        std::scanf("%d %d %d", &y, &z, &x);
        for (int j=0; j < 30; j++) {  // && z*t <= s && x != 0
            t = std::pow(2, j);
            
            if (x < t) {
                v.push_back(y*x); w.push_back(z*x); counter++; break;
            }
            
            v.push_back(y*t); w.push_back(z*t); counter++; x -= t;
        }
    }
    
    long arr[2][s+1]; std::memset(arr[0], 0, sizeof(arr[0])); arr[1][0] = 0;
    
    bool a=0, b=1;
    for (long i=1; i <= counter; i++) {
        a = 1-a, b = 1-b;
        for (long j=1; j <= s; j++) arr[a][j] = (j-w[i-1] >= 0) ? std::max(arr[b][j-w[i-1]]+v[i-1], arr[b][j]) : arr[b][j];
    }
    
    printf("%ld\n", arr[a][s]);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:8:58: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     std::vector<long> v, w; int s, n, x, y, z; std::scanf("%d %d", &s, &n); long counter = 0, t = 0;
      |                                                ~~~~~~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:11:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         std::scanf("%d %d %d", &y, &z, &x);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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