제출 #1183223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183223		iamhereforfun	Knapsack (NOI18_knapsack)	C++17	73 / 100	1095 ms	16796 KiB

knapsack

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(S) ((S) & -(S))

const int N = 2e3 + 5;
const int M = 2e5 + 5;
const int Q = 1e5 + 5;
const int LG = 20;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int B = 350;

int s, n;
long long dp[N], mx = 0;
vector<pair<long long, int>> obj;

void solve()
{
    cin >> s >> n;
    for (int x = 0; x < n; x++)
    {
        int v, w, k;
        cin >> v >> w >> k;
        for (int y = 0; y < LG; y++)
        {
            if (k == 0)
                break;
            if (k < (1 << y))
            {
                obj.push_back({k * v, k * w});
                break;
            }
            else
            {
                if ((1 << y) * w > s)
                    break;
                obj.push_back({(1 << y) * v, (1 << y) * w});
                k -= (1 << y);
            }
        }
    }
    memset(dp, 0, sizeof(dp));
    for (pair<long long, int> p : obj)
    {
        long long v = p.first;
        int i = p.second;
        for (int y = s; y >= i; y--)
        {
            dp[y] = max(dp[y], dp[y - i] + v);
            mx = max(mx, dp[y]);
        }
    }
    cout << mx;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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