Submission #780761

#	Time	Username	Problem	Language	Result	Execution time	Memory
780761		Kryz	Knapsack (NOI18_knapsack)	C++17	73 / 100	1077 ms	3976 KiB

knapsack

#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);
#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;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;
//}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27