제출 #1066486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066486		wood	Knapsack (NOI18_knapsack)	C++17	12 / 100	63 ms	31836 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> p32;
typedef pair<ll, ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<class T>
using Tree =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
#define int ll


signed main() {
    fast_cin();
    int s, n;
    cin >> s >> n;
    vp32 vp[s+1];
    for (int i = 0; i < n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        vp[w].eb(v, k);
    }
    int dp[s+1];
    fill(dp,dp+s+1,INT_MIN);
    dp[0] = 0;
    for (int i = 1; i <= s; i++) {
        if(vp[i].empty()) continue;
        sort(vp[i].begin(), vp[i].end());
        int weight = i;
        int cur = 0;
        int cnt = 0;
        auto ii = vp[i].rbegin();
        vector<vi> res(s,vi(s+1));
        while (cnt < (s+i-1)/i) {
            if (cnt >= ii->se) {
                ii++;
                if(ii==vp[i].rend())break;
                cnt = 0;
            }
            cur+=ii->fi;
            for(int j = 0; j<=s; j++) res[cnt][j] = dp[j];
            for(int j = 0; j<=s-weight; j++){
                res[cnt][j+weight] = max(res[cnt][j+weight],dp[j]+cur);
            }
            if(cnt) for(int j = 0; j<=s; j++) res[cnt][j] = max(res[cnt][j],res[cnt-1][j]);
            cnt++;
            weight += i ;
        }
        for(int j = 0; j<=s; j++) dp[j] = res[cnt-1][j];
    }
    for(int i = 1; i<=s; i++){
        dp[i] = max(dp[i],dp[i-1]);
    }
    cout<<dp[s]<<'\n';
    return 0;
}

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