제출 #491431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491431		CodigoL	Knapsack (NOI18_knapsack)	C++14	100 / 100	60 ms	2120 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair

#define forn(i,n) for(int i = 0;i<int(n);i++)
#define dforn(i,n) for(int i = int(n)-1;i>=0;i--)
#define forsn(i,s,n) for(int i = int(s);i<int(n);i++)
#define fore(i,s,n) for(int i = int(s);i<int(n);i++)
#define dforsn(i,s,n) for(int i = int(n)-1;i>=int(s);i--)

#define DBG(x) do{cout<<#x<<" = "<<x<<endl;}while(false)
#define TAM_MASK 1
#define get(mask,i) ((mask>>(TAM_MASK*(i)) & ( (1<<TAM_MASK)-1)))
#define set(mask,i,v)  ( ((mask & ~( ( (1<<TAM_MASK)-1) << (TAM_MASK*(i)) )) | (v<<(TAM_MASK * (i))) ))
#define popcount(mask) (__builtin_popcount(mask))
#define endl '\n'
#define ALL(x) x.begin(),x.end()
template<class T> ostream & operator<<(ostream & out, vector<T> & v)
{
    out<<"[";
    for(auto k : v) out<<k<<",";
    out<<"]"<<"\n";
    return out;
}
template<class T> ostream & operator<<(ostream & out, set<T>  s)
{
    out<<"{";
    for(auto k : s) out<<k<<",";
    out<<"}"<<"\n";
    return out;
}

template<class T, class U> ostream & operator<<(ostream & out, pair<T,U>  p)
{
    out<<"[ "<<p.first<<" , "<<p.second<<" ] ";
    return out;
}
template<class T, class U> istream & operator>>(istream & in, pair<T,U> & p)
{
    in>>p.first>>p.second;
    return in;
}


typedef long long intl;
const int maxs = 2005;
vector<pair<int,int> > ins[maxs];
vector<pair<int,int> > in;
intl dp[maxs];
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
    int S,N;
    cin>>S>>N;
    forn(i,N){
        int v,w,k;
        cin>>v>>w>>k;
        ins[w].pb({v,k});
    }
    forsn(i,1,maxs){
        sort(ins[i].begin(),ins[i].end());
        int t = S/i + 1;
        while(t and ins[i].size()){
            in.pb({i,ins[i].back().first});
            ins[i].back().second--;
            if(ins[i].back().second==0)
                ins[i].pop_back();
            t--;
        }
    }
    for(auto pp : in){
        int w = pp.first;
        int v = pp.second;
        dforn(i,S-w+1){
            dp[i+w] = max(dp[i+w],dp[i]+v);
        }
    }
    intl res = 0;
    forn(i,S+1) res = max(res,dp[i]);
    cout<<res<<endl;
}

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