제출 #638343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638343		slo	Knapsack (NOI18_knapsack)	C++14	100 / 100	81 ms	35184 KiB

knapsack

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

#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define numBit(x) (__builtin_popcountll(1ll*x))
#define getBit(x,i) ((x&(1<<i))?1:0)
#define Pi acos(-1.0l)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define ins insert
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()

#define ALLBITS ~0

typedef long long ll;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pill;
typedef pair<ll,int> plli;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

template<class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps=1e-9;
        if(x+eps<y){
            x=y; return true;
        }
        return false;
    }

template<class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps=1e-9;
        if(x>y+eps){
            x=y; return true;
        }
        return false;
    }

template<class X>
    X Abs(const X &x){
        return (x>0)?(x):(-x);
    }

/*-------------------MAIN PROGRAM------------------*/

const int MAXCAP=2007;
const ll INF=1e18;

int cap, n;
vpii grp[MAXCAP];

ll f[MAXCAP][MAXCAP];

void read(){
    cin>>cap>>n;
    while(n--){
        int v, w, k; cin>>v>>w>>k;
        grp[w].pb(mp(v,k));
    }
}

void solve(){
    rep(i,MAXCAP) rep(j,MAXCAP) f[i][j]=-INF;
    f[0][0]=0;
    ll ans=0;
    fore(curW,1,cap){
        f[curW][0]=0;
        sort(all(grp[curW]),greater<pii>());
        fore(lim,1,cap){
            f[curW][lim]=f[curW-1][lim];
            ll sum=0;
            int num=0, pos=0, used=0;
            while((num+1)*curW<=lim && pos<sz(grp[curW])){
                num++;
                sum+=grp[curW][pos].fi;
                if(f[curW-1][lim-num*curW]>=0)
                    maximize(f[curW][lim],
                             f[curW-1][lim-num*curW]+sum);
                used++;
                if(used==grp[curW][pos].se){
                    pos++;
                    used=0;
                }
            }
            maximize(ans,f[curW][lim]);
        }
    }
    cout<<ans;
}

int main(){
    fastIO;
    read();
    solve();
    return 0;
}

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