제출 #1305976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305976		timeflew	Knapsack (NOI18_knapsack)	C++20	100 / 100	58 ms	9068 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long

const int mxS=2e3;

ll dp[mxS+1];
map<ll, ll> mp[mxS+1];

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int s, n; cin>>s>>n;
    vector<array<ll, 3>> v(n);
    for(int i=0; i<n; i++) {
        cin>>v[i][0]>>v[i][1]>>v[i][2];//v, w, k
		mp[v[i][1]][v[i][0]]+=v[i][2];
    }
/*    for(int i=0; i<n; i++) {
        ll use=v[i][2];
        for(int j=1; use>0; j*=2) {
            ll x=min(use, j)*v[i][1];
            ll val=1ll*min(use, j)*v[i][0];
            for(int k=s; k>=x; k--) {
                dp[k]=max(dp[k], dp[k-x]+val);
                ans=max(ans, dp[k]);
            }
            use-=min(use, j);
        }
    }
*/
	for(int i=1; i<=s; i++) {
		int mx=s/i;
		for(auto it=mp[i].rbegin(); it!=mp[i].rend(); it++) {
			if(mx==0)
			 	break;
			auto [v, c]=*it;
			int use=min(mx, c);
			int base=1;
			c=use;
			while(c>0) {
				int tmp=min(c, base);
				for(int j=s; j>=tmp*i; j--) {
					dp[j]=max(dp[j], dp[j-tmp*i]+tmp*v);
				}
				c-=tmp;
				base*=2;
			}
			mx-=use;
		}
	}
  cout<<dp[s];
  return 0;
}

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