제출 #1110595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110595		Mike_Vu	Knapsack (NOI18_knapsack)	C++14	17 / 100	1 ms	512 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITJ(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 2005;
int s, n;
ll ans = 0;

namespace sub5{
    vector<pii> wgr[maxn];
    ll dp[maxn];
    void additem(ll v, int w) {
//        cout << "item " << v << ' ' << w << "\n";
        for (int i = s-w; i >= 0; i--) {
            maximize(dp[i+w], dp[i]+v);
        }
//        for (int i = 0; i <= s; i++) {
//            cout << i << ' ' << dp[i] << "\n";
//        }
    }
    void consbit(int v, int w, int k) {
        int sum;
        for (sum = 1; sum*2-1 <= k; sum <<= 1) {
            additem((ll)v*sum, w*sum);
        }
        int val = k-(sum*2-1);
        if (val > 0) {
            additem((ll)v*val, w*val);
        }
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            //pushback {v, k}
            int v, w, k;
            cin >> v >> w >> k;
            if (w > s) continue;
            if (w == s) {
                maximize(ans, (ll)v);
                continue;
            }
            wgr[w].pb({v, k});
        }
        memset(dp, 0, sizeof(dp));
        for (int w = 1; w < s; w++) {
            //consider wgr w
            int sumw = 0; //only before full
            sort(wgr[w].begin(), wgr[w].end(), greater<>());
            for (int i = 0; i < (int)wgr[w].size(); i++) {
                int v = wgr[w][i].fi, k = wgr[w][i].se;
                minimize(k, (s-sumw)/w);
                if (k <= 0) break;
                //solve
                consbit(v, w, k);
                //another break
                sumw += k*w;
                if ((s-sumw)/w <= 0) break;
            }
        }
        for (int i = 0; i <= s; i++) {
            maximize(ans, dp[i]);
        }
        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> s >> n;
//    if (n == 1) return sub1::solve(), 0;
    return sub5::solve(), 0;
}

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