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>
using namespace std;
#define ll long long
#define fi first
#define se second
#define sst string
#define pb push_back
#define maxco 100000+5
#define lld long double
#define cha ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ffl cout.flush();
#define phi acos(-1)
#define mod 707
#define mr make_pair
#define pqin priority_queue<ll,vector<ll>,greater<>>
#define pqpair priority_queue<pair<ll,ll> ,vector<pair<ll,ll>>,greater<pair<ll,ll>>>
#define pqpair2 priority_queue<pair<pair<ll,ll>,pair<ll,ll>>,vector<pair<pi,pair<ll,ll>>>,greater<pair<pi,pair<ll,ll>>>>
#define INF 1000000009
#define MAXN 1000069
#define pi pair<ll,ll>
ll mvx[]={1,-1,0,0};
ll mvy[]={0,0,1,-1};
float x,y;
clock_t time_req;
void st(){
time_req = clock();
}
void end(){
time_req = clock() - time_req;
cout << "Using pow function, it took " << (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
}
ll a[MAXN],b[MAXN],c[MAXN];
ll dp[MAXN];
int main(){
cha
ll n,x;
cin>>x>>n;
for(ll i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
}
for(ll i=x;i>=0;i--)dp[i]=-1e18;
dp[0]=0;
for(ll i=1;i<=n;i++){
for(ll j=x-b[i];j>=0;j--){
if(dp[j]!=-1e18){
ll cnt=1;
while(cnt<=c[i] && j+cnt*b[i]<=x){
dp[j+cnt*b[i]]=max(dp[j]+a[i]*cnt,dp[j+cnt*b[i]]);
cnt++;
}
}
}
}
ll ans=0;
for(ll i=x;i>=1;i--)ans=max(dp[i],ans);
cout<<ans;
}
//ll n,m,k,a[MAXN];
//map<ll,ll> cnt;
//ll val[MAXN][69];
//ll dp[MAXN][69];
//ll bck[MAXN][69];
//int main(){
// cin>>n>>m>>k;
// for(ll i=1;i<=n;i++){
// cin>>a[i];
// }
// for(ll i=0;i<=k;i++){
// cnt.clear();
// ll idx=1;
// ll t=0;
// for(ll j=1;j<=n;j++){
// cnt[a[j]]++;
// if(cnt[a[j]]>m)t++;
// while(t>i){
// if(cnt[a[idx]]>m)t--;
// cnt[a[idx]]--;
// idx++;
// }
// val[j][i]=idx-1;
// }
// }
//// for(ll j=0;j<=k;j++){
//// for(ll i=1;i<=n;i++){
//// cout<<j<<" "<<i<<" : "<<val[j][i]<<endl;
//// }
//// }
// for(ll j=1;j<=n;j++){
// for(ll i=0;i<=k;i++){
// if(j<=i){
// dp[j][i]=0;
// continue;
// }
// else{
// if(dp[val[j][i]][i-bck[j-1][i]]+1==dp[j-1][i]){
// //gabung
// dp[j][i]=dp[j-1][i];
// bck[j][i]=bck[j-1][i];
// }
// else if(dp[j-1][i-1]<dp[j-1][i]+1 && i>0){
// //dia bikin grup
// dp[j][i]=dp[j-1][i-1];
// bck[j][i]=bck[j-1][i-1]+1;
// }
// else{
// dp[j][i]=dp[j-1][i]+1;
// bck[j][i]=0;
// }
// }
// }
// }
//// for(ll i=0;i<=k;i++){
//// for(ll j=1;j<=n;j++){
//// cout<<i<<" "<<j<<" : "<<dp[j][i]<<endl;
//// }
//// }
// cout<<dp[n][k]<<endl;
//}
# | 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... |