제출 #1313939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313939		br1	Knapsack (NOI18_knapsack)	C++20	100 / 100	46 ms	1720 KiB

knapsack

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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define srt(x) sort(all(x))
#define rev(x) reverse(all(x))
#define rsrt(x) sort(rall(x))
#define sz(x) (int)x.size()
#define fi first
#define se second
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vvll = vector<vll>;

const ll inf=1e18;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll s, n; cin>>s>>n;
    
    map<int, vector<pair<int, int>>> by_w;
    for(int i=0; i<n; i++){
        int v, w, k; cin>>v>>w>>k;
        by_w[w].pb({v, k});
    }

    vll dp(s+1);
    for(auto &[w, items] : by_w){
        rsrt(items);
        for(int j=s; j>=w; j--){
            int c = 0, type = 0, used = 0;
            ll profit = 0;
            while((c+1)*w <= j && type < sz(items)){
                c++;
                profit += items[type].first;
                dp[j] = max(dp[j], dp[j-c*w]+ profit);
                used++;
                if(used == items[type].second){ type++; used = 0; }
            }
        }
        
    }
    
    cout<<dp[s]<<'\n';
}

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