Submission #1103396

#TimeUsernameProblemLanguageResultExecution timeMemory
1103396Mauricio_CruzKnapsack (NOI18_knapsack)C++14
29 / 100
2 ms520 KiB
#include <bits/stdc++.h> using namespace std; #define srtl(x)sort((x).begin(),(x).end()) #define srtg(x)sort((x).begin(),(x).end(),greater<>()) #define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define f first #define s second #define pb push_back #define pii pair<int,int> #define ins insert #define vi vector<int> #define vii vector<pii> #define viii vector<pair<int,pii>> int ax[4]={0,1,0,-1}; int ay[4]={1,0,-1,0}; #define int long long int32_t main(){ ios; int k,n; cin>>k>>n; int a[n][3]; viii v(n); for(int i=0;i<n;i++){ cin>>v[i].f>>v[i].s.f>>v[i].s.s; } srtg(v); for(int i=0;i<n;i++){ a[i][0]=v[i].f; a[i][1]=v[i].s.f; a[i][2]=v[i].s.s; } vector<int>dp(k+1,0); for(int i=0;i<n;i++){ for(int j=k;j>=a[i][1];j--){ int mul=1; int a2=a[i][2]; bool xd=1; for(int l=j-a[i][1];l>=0&&a2!=0&&xd;l-=a[i][1],a2--){ xd=0; if(dp[j]<=dp[l]+(a[i][0]*mul)){ xd=1; dp[j]=dp[l]+(a[i][0]*mul); } mul++; } } } cout<<dp[k]; 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...