제출 #1313437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313437		inifnite	Knapsack (NOI18_knapsack)	C++20	17 / 100	1 ms	332 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<ll>
#define pb push_back
#define ii pair<int,int>
#define f first
#define s second
 
const int N=2001;
const ll INF=1e18;
 
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
 
void solve() {
    int n,x; cin>>x>>n;
    ll h[n],p[n],k[n];

    for(int i=0; i<n; i++) cin>>p[i]>>h[i]>>k[i];

    vi nw[N];
    for(int i=0; i<n; i++) {
        int q=(int)log2(k[i]);
        ll left=k[i]-(1<<q) + 1;

        // cout<<k[i]<<" --> "<<q<<" "<<left<<"\n";

        for(int j=0; j<q && ((1ll<<j)*h[i] <=x); j++)  nw[(1ll<<j)*h[i]].pb((1ll<<j)*p[i]);
        if(left) nw[left*h[i]].pb(left*p[i]);
    }
    for(int i=0; i<N;i++) if(nw[i].size()) {
        sort(nw[i].begin(), nw[i].end(), greater<>());
        // for(auto j:nw[i]) cout<<j<<" ";
        //     cout<<"\n";
    }

    ll dp[x+1]={0};
    for(ll p=0; p<=x; p++) {
        for(auto i:nw[p]) {
            bool change=false;
            for(ll j=x-p; j>=0; j--) if(dp[j+p] < dp[j]+i) {
                dp[j+p] = dp[j]+i;
                change=true;
            }
            if(!change) break;
        }
    }

    ll ans=0;
    for(int i=0; i<=x; i++) ans=max(ans, dp[i]);
    cout<<ans<<"\n";
}
 
int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("nocross.in","r",stdin);
    // freopen("nocross.out","w",stdout);
    // #endif
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t = 1;
    while (t--) solve();
    return 0;
}

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