This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |