제출 #788927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788927		codergirl	Knapsack (NOI18_knapsack)	C++14	73 / 100	1074 ms	17456 KiB

knapsack

#include <iostream>
#include <vector>

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);
    
    std::vector<long> v, w; 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) {
                    v.push_back(y*x); w.push_back(z*x); counter++;
                }
                break;
            } else {
                if (z*t > s) break;
                v.push_back(y*t); w.push_back(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;
    
    for (long i=1; i <= counter; i++) {
        for (long j=1; j <= s; j++) {
            if (j-w[i-1] >= 0) arr[i%2][j] = std::max(arr[(i-1)%2][j-w[i-1]]+v[i-1], arr[(i-1)%2][j]);
            else arr[i%2][j] = arr[(i-1)%2][j];
        }
    }
    
    std::cout << arr[counter%2][s] << '\n';
}

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