제출 #463611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
463611		Duy_e	Knapsack (NOI18_knapsack)	C++14	컴파일 에러	0 ms	0 KiB

knapsack

/*THINK GONNA FAIL ? IF U DIDNT FAIL THEN WHAT IS THE POINT OF LEARNING */
#include <bits/stdc++.h>
#define ll long long
#define pii pair<long long, long long>
#define ull unsigned long long
#define st first
#define nd second
#define lower_case_alphabet "abcdefghijklmnopqrstuvwxyz"
#define upper_case_alphabet "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define file "test"
using namespace std;
const long long oo = 1e18;
const long long N = 1e5 + 5;

ll n, cnt, dp[N], A[N];
int s;
vector <pii> d[2004];

void decompose(int x){
    if (x == 0){ 
        cnt = -1;
        return;
    }
    cnt = 0;
    ll sum = 1;
    while (x > sum){
        x -= sum;
        A[cnt++] = sum;
        sum <<= 1;
    }
    A[cnt] = x;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> s >> n;

    for (int i = 1, v, w, k; i <= n; i ++){
        cin >> v >> w >> k;
        k = min(k, s/w + 1);
        d[w].push_back({v, k});
    }

    for (int i = 1; i <= s; i ++)
    if (d[i].size())
        sort(d[i].begin(), d[i].end(), greater<pii> ());
        int out = 0;
        for (pii p: d[i]){
            if (s/i < out) break;
            out ++;
            decompose(p.nd);
            for (ll W, V; cnt >= 0; cnt --){
                W = A[cnt]*i, V = A[cnt]*p.st;
                for (int j = s; j >= W; j --)
                    dp[j] = max(dp[j], dp[j-W] + V);
            }
        }

    cout << dp[s];

    return 0;
}    
// sketch out every idea before see any solution, it helps alots.
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:47:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   47 |     if (d[i].size())
      |     ^~
knapsack.cpp:49:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |         int out = 0;
      |         ^~~
knapsack.cpp:50:23: error: 'i' was not declared in this scope
   50 |         for (pii p: d[i]){
      |                       ^