제출 #891180

#제출 시각아이디문제언어결과실행 시간메모리
891180Younis_DwaiKnapsack (NOI18_knapsack)C++14
73 / 100
1056 ms2680 KiB
#include <bits/stdc++.h> #define int long long #define in insert #define F first #define S second #define pb push_back #define endl "\n" //#define mid (l+r)/2 #define all(v) v.begin(),v.end() //#define pop pop_back using namespace std; const int M=998244353; int s,n,dp[2009],b[100009][3],dp2[2009],p[11]; bool vis[2009]; int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); p[0]=1; for(int i=1;i<=10;i++) p[i]=p[i-1]*10; cin>>s>>n; for(int i=1;i<=n;i++){ string s1,s2,s3; cin>>s1>>s2>>s3; int sum=0; for(int j=s1.size()-1;j>=0;j--){ sum+=((int)s1[j]-(int)'0')*p[s1.size()-1-j]; } b[i][0]=sum; sum=0; for(int j=s2.size()-1;j>=0;j--){ sum+=((int)s2[j]-(int)'0')*p[s2.size()-1-j]; } b[i][1]=sum; sum=0; for(int j=s3.size()-1;j>=0;j--){ sum+=((int)s3[j]-(int)'0')*p[s3.size()-1-j]; } b[i][2]=sum; for(int j=0;j<=s;j++) vis[j]=0; for(int j=s;j>=0;j--){ if(vis[j]) break; deque<pair<int,int>> q; for(int k=0;k<=b[i][2];k++){ if(k*b[i][1]>j) break; int val=dp[j-k*b[i][1]]+b[i][0]*k; while(!q.empty()){ if(q.front().F<=val) q.pop_front(); else break; } q.push_front({val,j-b[i][1]*k}); } vis[j]=1; dp[j]=q.back().F; for(int k=1;k<=2001;k++){ if(j-k*b[i][1]<0) break; int cur=j-k*b[i][1]; vis[cur]=1; if(q.back().S>cur) q.pop_back(); if(cur-b[i][2]*b[i][1]>=0){ int val=dp[cur-b[i][2]*b[i][1]]+b[i][0]*(b[i][2]+k); while(!q.empty()){ if(q.front().F<=val) q.pop_front(); else break; } q.push_front({val,cur-b[i][2]*b[i][1]}); } dp[cur]=q.back().F-k*b[i][0]; } } } cout<<dp[s]; 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...