Submission #1163116

#TimeUsernameProblemLanguageResultExecution timeMemory
116311669godKnapsack (NOI18_knapsack)C++20
0 / 100
2 ms1864 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long #define float long double #define ff first #define ss second #define endl "\n" #define oyes cout<<"YES"<<endl; #define ono cout<<"NO"<<endl; #define vi vector <int> #define all(a) a.begin(),a.end() #define vin(v,n) int x;for(int i=0;i<n;i++){cin>>x;v.push_back(x);} #define dis(s,n) for(int i=0;i<n;i++){cout<<s[i]<<" ";}cout<<"\n"; using namespace std; using namespace __gnu_pbds; vector<int> sexp(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;} typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;//if use greater not less get desc void decToBinary(int n){ vi bin(32,0); int i = 0; while (n > 0) { bin[i] = n % 2; n = n / 2; i++;} for (int j = i - 1; j >= 0; j--) cout << bin[j];} long long exp(long long a, long long b) { long long res = 1; while (b > 0) { if (b & 1) {res = res * a;} a = a * a; b >>= 1;} return res;} long long exp1(long long a, long long b) { long long mod=1e9+7; a%=mod; long long res = 1; while (b > 0) { if (b & 1) {res = res * a%mod;} a = a * a%mod; b >>= 1;} return res;} signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int s,n; cin>>s>>n; vector<pair<int,pair<int,int>>> vpp; for(int i=0;i<n;i++){ int x,y,z; cin>>x>>y>>z; vpp.push_back({x,{y,z}}); } if(n==1){ int d=s/vpp[0].first; cout<<min(vpp[0].second.second,d)*(vpp[0].second.first); return 0; } vector<pair<int,int>> vp; for(auto it:vpp){ int q=it.second.second; int cost=it.second.first; int reward=it.first; int cur=1; while(q>0){ vp.push_back({cost*min(cur,q),reward*min(cur,q)}); q=q-cur; cur=cur*2; } } sort(vp.begin(),vp.end()); // for(auto it:vp){ // cout<<it.first<<" "<<it.second<<endl; // } //return 0; //vector<int> dp(s+1,0); int damn=vp.size(); vector<vector<int>> dp(s+1,vector<int>(damn+1,0)); for(int i=1;i<=damn;i++){ for(int j=1;j<=s;j++){ if(vp[i-1].first<=j){ dp[j][i]=max(dp[j][i],vp[i-1].second+dp[j-vp[i-1].first][i-1]); } } } int maxi=0; for(int j=0;j<=s;j++){ for(int i=0;i<=damn;i++){ maxi=max(maxi,dp[j][i]); } } cout<<maxi; return 0; }
#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...