Submission #789547

#	Time	Username	Problem	Language	Result	Execution time	Memory
789547		codergirl	Knapsack (NOI18_knapsack)	C++14	0 / 100	119 ms	262144 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("%d %d", &s, &n); long t = 0;
    
    for (int i=0; i < n; i++) {
        std::scanf("%d %d %d", &y, &z, &x);
        for (int j=0; j < 30 && z*t <= s && x != 0; 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 (int i=0; i < v.size(); i++) {
        printf("%ld %ld\n", v[i], w[i]);
    }*/
    
    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:8:62: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long int*' [-Wformat=]
    8 |     std::vector<long> v, w; long s, n, x, y, z; std::scanf("%d %d", &s, &n); long t = 0;
      |                                                             ~^      ~~
      |                                                              |      |
      |                                                              int*   long int*
      |                                                             %ld
knapsack.cpp:8:65: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long int*' [-Wformat=]
    8 |     std::vector<long> v, w; long s, n, x, y, z; std::scanf("%d %d", &s, &n); long t = 0;
      |                                                                ~^       ~~
      |                                                                 |       |
      |                                                                 int*    long int*
      |                                                                %ld
knapsack.cpp:11:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long int*' [-Wformat=]
   11 |         std::scanf("%d %d %d", &y, &z, &x);
      |                     ~^         ~~
      |                      |         |
      |                      int*      long int*
      |                     %ld
knapsack.cpp:11:25: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long int*' [-Wformat=]
   11 |         std::scanf("%d %d %d", &y, &z, &x);
      |                        ~^          ~~
      |                         |          |
      |                         int*       long int*
      |                        %ld
knapsack.cpp:11:28: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long int*' [-Wformat=]
   11 |         std::scanf("%d %d %d", &y, &z, &x);
      |                           ~^           ~~
      |                            |           |
      |                            int*        long int*
      |                           %ld
knapsack.cpp:34:22: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     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("%d %d", &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("%d %d %d", &y, &z, &x);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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