Submission #463581

#	Time	Username	Problem	Language	Result	Execution time	Memory
463581		Duy_e	Knapsack (NOI18_knapsack)	C++14	0 / 100	2 ms	332 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 = 2e5 + 5;

ll s, n, w[N], v[N], k[N], cnt, dp[N], A[N];

vector <pii> d[2004];

void decomposition(int x){
    if (x == 0){ 
        cnt = -1;
        return;
    }
    cnt = 0;
    int 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);
    #ifndef ONLINE_JUDGE
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    #endif
    
    cin >> s >> n;

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

    for (int i = 0; i <= s; i ++){
        for (pii p: d[i]){
            decomposition(p.nd);
            for (; cnt >= 0; cnt --){
                ll 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
**/

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(file".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(file".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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