Submission #879437

#	Time	Username	Problem	Language	Result	Execution time	Memory
879437		proteam23	Knapsack (NOI18_knapsack)	C++14	100 / 100	43 ms	5164 KiB

knapsack

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <ctype.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define getbit(x,y) (((x)>>(y))&1)
#define turnon(x,y) ((x)|(1<<y))
#define turnof(x,y) ((x)^(1<<y))
#define oo 1000000000000000000
#define pb push_back
#define all(x) x.begin(),x.end()
#define con(mask) mask=(mask-1)&mask
#define Unique(val) val.erase(unique(val.begin(),val.end()),val.end())

const int mod=1e9+7;
const int base = 317;
const int Base = 100000;
using namespace std;

int n, S;
vector<ii>e[2005];

int dp[2005];

signed main()
{

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> S >> n;

    for(int i = 1; i <= n; i++) {
        int v, w, k;
        cin >> v >> w >> k;

        ii tmp;
        tmp.fi = v, tmp.se = k;

        e[w].pb(tmp);
    }

    for(int w = 1; w <= S; w++) {
        if(e[w].size()) {
            sort(all(e[w]));


            int cnt = S / w;

            //cout << e[w][0].fi << "\n";


            for(int vt = e[w].size() - 1; vt >= 0; vt--) {

                int V = e[w][vt].fi;

                //cout << V << "\n";
                if(cnt > e[w][vt].se) {
                    cnt -= e[w][vt].se;

                    

                    for(int i = 1; i <= e[w][vt].se; i++) {
                        for(int j = S; j >= w; j--) {
                            dp[j] = max(dp[j], dp[j - w] + V);
                        }
                    }
                }
                else {

                    for(int i = 1; i <= cnt; i++) {
                        for(int j = S; j >= w; j--) {
                            dp[j] = max(dp[j], dp[j - w] + V);
                        }
                    }

                    break;
                }
            }
        }
    }

    cout << dp[S];


}
//      ProTeam
//(¯`·.·´¯) (¯`·.·´¯)
//`·.¸(¯`·.·´¯)¸ .·
//×°× ` ·.¸.·´ ×°×

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