제출 #1151127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151127		danglayloi1	Knapsack (NOI18_knapsack)	C++20	100 / 100	104 ms	28108 KiB

knapsack

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
const int LG=30;
int n, m, w[nx], v[nx], t[nx];
ll ans=0, dp[2005];
vector<pair<ll, int>> a;
vector<ll> f[2005];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>m>>n;
    for(int i = 1; i <= n; i++)
        cin>>v[i]>>w[i]>>t[i];
    for(int i = 1; i <= n; i++)
    {
        t[i]=min(t[i], m/w[i]);
        for(int j = 0; j <= LG; j++)
        {
            if(t[i]>=(1<<j))
            {
                t[i]-=(1<<j);
                if(1ll*w[i]*(1<<j)<=m)
                    a.emplace_back(1ll*v[i]*(1<<j), w[i]*(1<<j));
            }
        }
        if(t[i]>=0 && 1ll*w[i]*t[i]<=m)
            a.emplace_back(1ll*v[i]*t[i], w[i]*t[i]);
    }
    for(auto it:a)
        f[it.se].emplace_back(it.fi);
    a.clear();
    for(int i = 1; i <= m; i++)
    {
        sort(f[i].begin(), f[i].end(), greater<ll>());
        while(f[i].size()>m/i)
            f[i].pop_back();
        for(ll x:f[i])
            a.emplace_back(x, i);
    }
    for(auto it:a)
        for(int i = m; i >= it.se; i--)
            dp[i]=max(dp[i], dp[i-it.se]+it.fi);
    cout<<*max_element(dp, dp+m+1);
}

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