Submission #1145812

#TimeUsernameProblemLanguageResultExecution timeMemory
1145812vinod_h332004Knapsack (NOI18_knapsack)C++20
100 / 100
94 ms33096 KiB
#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 }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...