Submission #1145812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145812		vinod_h332004	Knapsack (NOI18_knapsack)	C++20	100 / 100	94 ms	33096 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vvll vector<vll>
#define vii vector<int>
#define vvii vector<vii>
#define vecs vector<string>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define vbl vector<bool>
#define vvbl vector<vector<bool>>
#define setpll set<pll>
#define setpii set<pii>
#define forl(i,a,b) for(ll i=a;i<b;i++)
#define fori(i,a,b) for(int i=a;i<b;i++)
#define rforl(i,a,b) for(ll i=a;i>b;i--)
#define rfori(i,a,b) for(int i=a;i>b;i--)
#define sz(a) a.size()
#define pb push_back
#define eb emplace_back
#define lexi lexicographical_compare
#define all(x) (x).begin(), (x).end()
#define suml(v) accumulate(all(v),0LL)
#define sumi(v) accumulate(all(v),0)
#define lb(v,target) lower_bound(all(v), target);
#define ub(v,target) upper_bound(all(v), target);
#define JOIN_STRINGS(vec) std::accumulate((vec).begin(), (vec).end(), std::string(""))
#define vin0(v) for(ll i=0; i<(ll)v.size(); i++) cin>>v[i];
#define vin1(v) for(ll i=1; i<(ll)v.size(); i++) cin>>v[i];
#define vini0(v) for(int i=0; i<(int)v.size(); i++) cin>>v[i]
#define vini1(v) for(int i=1; i<(int)v.size(); i++) cin>>v[i];
#define vout0(v) for(ll i=0; i<(ll)v.size(); i++) cout<<v[i]<<' '
#define vout1(v) for(ll i=0; i<(ll)v.size(); i++) cout<<v[i]<<' '
#define vouti0(v) for(int i=0; i<(ll)v.size(); i++) cout<<v[i]<<' '
#define vouti1(v) for(int i=1; i<(ll)v.size()+1; i++) cout<<v[i]<<' '
#define fastIO() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF INT32_MAX
const int MOD=1e9+7;
const int MAX_N = 100005;
#define add(a,b) a=(a+(b))%MOD
using namespace std;



//Tarjans Bridge Finding algo
// int bridgec;
// vector<int> adj [MAX_N];
// int dfs [MAX_N];
// int low [MAX_N];
// int cur;
//
// void visit (int vertex, int parent) {
//     cur++;
//     dfs[vertex] = cur;
//     low[vertex] = cur;
//
//     for (int nxt : adj[vertex]) {
//         if (dfs[nxt] == 0) {
//             visit(nxt, vertex);
//             low[vertex] = min(low[vertex], low[nxt]);
//             if (low[nxt] > dfs[vertex]) {
//                 bridgec++;
//             }
//         } else if (nxt != parent) {
//             low[vertex] = min(low[vertex], dfs[nxt]);
//         }
//     }
// }
// void setIO(string name = "") {
//     if (name.size()) {
//         freopen((name + ".in").c_str(), "r", stdin);
//         freopen((name + ".out").c_str(), "w", stdout);
//     }
// }
int main () {
    fastIO();
    int s,n;cin>>s>>n;
    map<int,vpii>weight;
    fori(i,0,n) {
        int v,w,k;cin>>v>>w>>k;
        if (w<=s && v>0) weight[w].pb({v,k});
    }
    vvll dp(weight.size()+1,vll(s+1,INT32_MIN));
    dp[0][0]=0;
    int pos=1;
    for (auto [w,items]:weight) {
        sort(all(items),greater<pii>());
        fori(i,0,s+1) {
            dp[pos][i]=dp[pos-1][i];
            ll profit=0;
            int tot_copies=0;
            int curr_copies=0;
            int items_iter=0;
            while ((tot_copies+1)*w<=i && items_iter<items.size()) {
                tot_copies++;
                profit += items[items_iter].first;
                if (dp[pos-1][i-(tot_copies*w)]!=INT32_MIN) {
                    dp[pos][i]=max(dp[pos][i],dp[pos-1][i-(tot_copies*w)]+profit);
                }
                curr_copies++;
                if (curr_copies==items[items_iter].second) {
                    curr_copies=0;
                    items_iter++;
                }
            }
        }
        pos++;
    }
    cout << *max_element(dp.back().begin(),dp.back().end()) << endl;


    //dp[i][j]=max value till ith weight type and j weight = max(dp[i][j],dp[i-1][j-(copies*w[i])]+profit


}

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