Submission #788890

#	Time	Username	Problem	Language	Result	Execution time	Memory
788890		codergirl	Knapsack (NOI18_knapsack)	C++14	73 / 100	28 ms	57932 KiB

knapsack

#include <iostream>

long ceil_log2(unsigned long long x) {
    static const unsigned long long t[6] = {0xFFFFFFFF00000000ull, 0x00000000FFFF0000ull, 0x000000000000FF00ull, 0x00000000000000F0ull, 0x000000000000000Cull, 0x0000000000000002ull};
    
    long y = (((x & (x - 1)) == 0) ? 0 : 1), j = 32;
    
    for (long i = 0; i < 6; i++) {
        long k = (((x & t[i]) == 0) ? 0 : j); y += k;
        x >>= k; j >>= 1;
    }
    return y;
}

long pow(long x, long p) {
  if (p == 0) return 1;
  if (p == 1) return x;
  
  long tmp = pow(x, p/2);
  if (p%2 == 0) return tmp * tmp;
  else return x * tmp * tmp;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    
    long v[800000], w[800000]; long s, n; std::cin >> s >> n;
    
    long counter = 0, x, t, y, z;
    for (long i=0; i < n; i++) {
        std::cin >> y >> z >> x;
        for (long j=0; j <= 30; j++) {
            if (x == 0) break;
            t = pow(2, j);
            if (x < t) {
                v[counter] = y*x; w[counter] = z*x; counter++; break;
            } else {
                //std::cout << "hi!\n";
                //std::cout << y << ' ' << z << ' ' << t << '\n';
                v[counter] = y*t; w[counter] = z*t; counter++; x -= t;
                //std::cout << counter-1 << ' ' << v[counter-1] << ' ' << w[counter-1] << '\n';
            }
        }
    }
    
    long arr[counter+1][s+1];
    for (long i=1; i <= counter; i++) {
        arr[i][0] = 0;
        for (long j=0; j <= s; j++) {
            arr[0][j] = 0;
            if (j-w[i-1] >= 0) arr[i][j] = std::max(arr[i-1][j-w[i-1]]+v[i-1], arr[i-1][j]);
            else arr[i][j] = arr[i-1][j];
        }
    }
    /*
    for (long i=0; i <= counter; i++) {
        for (long j=1; j <= s; j++) {
            std::cout << arr[i][j] << ' ';
        }
        std::cout << '\n';
    }*/
    
    std::cout << arr[counter][s] << '\n';
}

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