Submission #788940

#	Time	Username	Problem	Language	Result	Execution time	Memory
788940		codergirl	Knapsack (NOI18_knapsack)	C++14	73 / 100	17 ms	10580 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[300000], w[300000]; int s, n; std::cin >> s >> n;
    
    long counter = 0, t; int x, y, z;
    for (int i=0; i < n; i++) {
        std::cin >> y >> z >> x;
        for (int j=0; j <= 30; j++) {
            if (x == 0) break;
            t = pow(2, j);
            if (x < t) {
                if (z*x > s) break;
                v[counter] = y*x; w[counter] = z*x; counter++; break;
            } else {
                if (z*t > s) break;
                v[counter] = y*t; w[counter] = z*t; counter++; x -= t;
            }
        }
    }
    
    long arr[2][s+1];
    for (long j=0; j <= s; j++) arr[0][j] = 0;
    arr[1][0] = 0;
    
    int a=0, b=1;
    for (long i=1; i <= counter; i++) {
        std::swap(a, b);
        for (long j=1; j <= s; j++) {
            if (j-w[i-1] >= 0) arr[a][j] = std::max(arr[b][j-w[i-1]]+v[i-1], arr[b][j]);
            else arr[a][j] = arr[b][j];
        }
    }
    
    std::cout << arr[a][s] << '\n';
}

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