Submission #1322498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322498		dinh_vu_bao_2009	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	332 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define task ""
#define f first
#define s second
#define FOR(i,a,b) for(int i = a;i<=b;i++)
#define FOU(i,a,b) for(int i = a;i>=b;i--)
#define times cerr<<endl<<"time:"<<(1.0*clock())/CLOCKS_PER_SEC<<endl;
mt19937 rng(time(nullptr));
int rand(int l,int r){return l+rng()%(r-l+1);}


using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;



template<class X,class Y>
    bool maximize(X &x,const Y &y){
    if(x<y){
        x = y;
        return false;
    }else return true;
    }
template<class X,class Y>
    bool minimize(X &x,const Y &y){
    if(x>y){
        x = y;
        return false;
    }else return true;
    }




const int sz = 1e5+5;
const int mz = 2e2+5;
int n,S;
ll dp[mz];
ll w[mz],vl[mz],k[mz],used[mz];

bool cmp(const int &a,const int &b){
return vl[a]>vl[b];
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>S>>n;
FOR(i,1,n)cin>>vl[i]>>w[i]>>k[i];

vi ord(n);
iota(ord.begin(),ord.end(),1);
sort(ord.begin(),ord.end(),cmp);

for(int i:ord){
    FOR(it,1,k[i]){
    if(used[w[i]]*w[i]>S)break;
    FOU(j,S,w[i])maximize(dp[j],dp[j-w[i]]+vl[i]);
    used[w[i]]++;
    }
}
cout<<dp[S];

}

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