Submission #789611

#	Time	Username	Problem	Language	Result	Execution time	Memory
789611		codergirl	Knapsack (NOI18_knapsack)	C++14	73 / 100	1070 ms	16276 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, t=0; std::scanf("%ld %ld", &s, &n); long arr[2][s+1]; std::memset(arr[0], 0, sizeof(arr[0])); arr[1][0] = 0; bool a=1, b=0;
    
    for (int i=0; i < n; i++) {
        std::scanf("%ld %ld %ld", &y, &z, &x);
        for (int j=0; j < 30; j++) {
            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;
        }
    }
    
    for (long i=1; i <= v.size(); i++, a = 1-a, b = 1-b) for (int 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];
    /*
    for (int i=0; i < 2; i++) {
        for (int j=0; j <= s; j++) {
            printf("%ld ", arr[i][j]);
        }
        printf("\n");
    }
    */
    printf("%ld\n", arr[b][s]);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:27:22: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (long i=1; i <= v.size(); i++, a = 1-a, b = 1-b) for (int 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];
      |                    ~~^~~~~~~~~~~
knapsack.cpp:8:64: 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, t=0; std::scanf("%ld %ld", &s, &n); long arr[2][s+1]; std::memset(arr[0], 0, sizeof(arr[0])); arr[1][0] = 0; bool a=1, b=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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27