Submission #789580

#	Time	Username	Problem	Language	Result	Execution time	Memory
789580		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; long s, n, x, y, z; std::scanf("%ld %ld", &s, &n);// long t = 0;
    
    for (int i=0; i < n; i++) {
        std::scanf("%ld %ld %ld", &y, &z, &x);
        for (long j=0, t=std::pow(2,j); j < 30; j++) { // && z*t <= s && x != 0
            
            //t = std::pow(2, j);
            
            if (z*t > s) break;
            
            if (x < t) {
                v.push_back(y*x); w.push_back(z*x); break;
            }
            
            v.push_back(y*t); w.push_back(z*t); x -= t;
            
            if (x == 0) break;
        }
    }
    
    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 <= v.size(); 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:31:22: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (long i=1; i <= v.size(); i++) {
      |                    ~~^~~~~~~~~~~
knapsack.cpp:8:59: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     std::vector<long> v, w; long s, n, x, y, z; std::scanf("%ld %ld", &s, &n);// long 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("%ld %ld %ld", &y, &z, &x);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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