Submission #1126676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126676		ttd	Knapsack (NOI18_knapsack)	C++17	49 / 100	287 ms	327680 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOD(i,a,b) for(int i=a;i>=b;i--)
#define MASK(mask,n) for(int mask=0;mask<(1<<n);mask++)
#define SUB(submask,mask) for(int submask=(mask-1)&mask;submask>0;submask=(submask-1)&mask)
#define pb push_back
#define sz(a) ((int)a.size()-1)
clock_t start,finish;
const int MOD=1e9+7;
const int Nall=1e5+5;
int n,s,V[Nall],W[Nall],K[Nall];
int add(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
namespace subcheck{
    bool sub1(){return n==1;}
    bool sub2(){
        FOR(i,1,n){
            if(K[i]>1) return 0;
        }
        return n<=100;
    }
    bool sub3(){
        FOR(i,1,n){
            if(K[i]>10) return 0;
        }
        return n<=100;
    }
    bool sub4(){
        return n<=100;
    }
}
namespace sub1{
    void solve(){
        cerr<<"SUB1";
        cout<<min(K[1],s/W[1])*V[1];
    }
}
namespace sub2{
    const int N=1e2+5,S=2e3+5;
    int Dp[N][S];
    void solve(){
        cerr<<"SUB2 ";
        int res=0;
        if(W[1]<=s) Dp[1][W[1]]=V[1],res=V[1];
        FOR(i,2,n){
            FOR(j,1,i-1){
                FOR(w,1,s){
                    if(w-W[i]>=0) Dp[i][w]=max(Dp[i][w],Dp[j][w-W[i]]+V[i]);
                }
            }
            FOR(w,1,s) res=max(res,Dp[i][w]);
        }
        cout<<res;
    }
}
namespace sub3{
    const int S=2e3+5,N=1e3+5;
    int Dp[N][S];
    void solve(){
        cerr<<"SUB3 ";
        int m=n;
        FOR(i,1,n){
            K[i]--;
            while(K[i]--){V[++m]=V[i],W[m]=W[i];}
        }
        FOR(w,W[1],s) Dp[1][w]=V[1];
        FOR(i,2,m){
            FOR(w,1,s){
                Dp[i][w]=max(Dp[i][w-1],Dp[i-1][w]);
                if(w-W[i]>=0) Dp[i][w]=max(Dp[i][w],Dp[i-1][w-W[i]]+V[i]);
            }
        }
        cout<<Dp[m][s];
    }
}
namespace sub4{
    const int S=2e3+5,N=2e4+5;
    int Dp[N][S];
    void solve(){
        int m=n;
        FOR(i,1,n){
            K[i]=min(K[i],s/W[i]);
            K[i]--;
            while(K[i]--){V[++m]=V[i],W[m]=W[i];}
        }
        FOR(w,W[1],s) Dp[1][w]=V[1];
        FOR(i,2,m){
            FOR(w,1,s){
                Dp[i][w]=max(Dp[i][w-1],Dp[i-1][w]);
                if(w-W[i]>=0) Dp[i][w]=max(Dp[i][w],Dp[i-1][w-W[i]]+V[i]);
            }
        }
        cout<<Dp[m][s];
    }
}
signed main(){
    start=clock();
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>s>>n;
    FOR(i,1,n) cin>>V[i]>>W[i]>>K[i];
    if(subcheck::sub1()) return sub1::solve(),0;
    if(subcheck::sub2()) return sub2::solve(),0;
    if(subcheck::sub3()) return sub3::solve(),0;
    if(subcheck::sub4()) return sub4::solve(),0;
    return 0;
}

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