제출 #1252618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252618		dfscp	Knapsack (NOI18_knapsack)	C++20	73 / 100	1098 ms	98872 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
#define nl '\n'
#define f0(i,a,b) for (int i = a, _b = b; i < _b; i++)
#define f1(i,a,b) for (int i = a, _b = b; i <= _b; i++)
#define rf(i,a,b) for (int i = a, _b = b; i >=_b; i--)
#define fi first
#define se second
#define file(Name) freopen(Name".inp", "r", stdin); freopen(Name".out", "w", stdout);
#define Size(a) (int)a.size()
#define bit(mask, i) ((mask>>i)&1)

using namespace std;

const int Maxn = 1e5+5;
const int mod = 1e9+7;
const int inf32 = 2e9+5;
const long long inf64 = 2e18+7;

struct NODE
{
    ll v, w, k;
};

int s, n;
vector<NODE> g;
ll f[Maxn];

void process(int pos)
{
    ll p = 1, tmp = g[pos].k;
    while(tmp >= p)
    {
        tmp -= p;
        g.push_back({g[pos].v, g[pos].w,p});
        p*=2;
    }
    g[pos].k = tmp;
    if (tmp) process(pos);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen("test.inp", "r", stdin); freopen("hoc.out", "w", stdout);
    cin >> s >> n;
    f1(i,1,n)
    {
        int v, w, k; cin >> v >> w >> k;
        g.push_back({v,w,k});
    }
    f0(i,0,n) process(i);
    int st = n;
    f[0] = 0;
    f0(i,st,g.size())
    {
        rf(j,s,min(g[i].w*g[i].k, 11ll*s+1))
        {
            f[j] = max(f[j], f[j-g[i].w*g[i].k] + g[i].v*g[i].k);
        }
    }
    cout << f[s];
    return 0;
}

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