Submission #474843

#	Time	Username	Problem	Language	Result	Execution time	Memory
474843		BackNoob	Knapsack (NOI18_knapsack)	C++14	100 / 100	73 ms	7416 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define task "name"
#define ull unsigned long long
using namespace std;
const ll mxN = 220797 + 7;
const ll inf = 1e9 + 277;
const ll mod = 2147483648;
const ll infll = 1e18 + 7;
const ll base = 307;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct item{
	ll v , w , k;
} a[mxN];

ll dp[3000];
vector<pair<ll , ll>> val[3000];
vector<ll> pre[3000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("task.inp" , "r" , stdin);
    //freopen("task.out" , "w" , stdout);
    
    int s , n;
    cin >> s >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i].v >> a[i].w >> a[i].k;

    for(int i = 1 ; i <= n ; i++) {
    	val[a[i].w].push_back({a[i].v , a[i].k});
    }

    for(int i = 1 ; i <= s ; i++) {
    	sort(val[i].begin() , val[i].end() , greater<pair<ll,ll>>());
    	int cnt = 0;
    	ll cur = 0;
    	for(auto it : val[i]) {
    		for(int j = 1 ; j <= it.se ; j++) {
    			pre[i].push_back(cur + it.fi);
    			cur += it.fi;
    			++cnt;
    			if(cnt * i > s) break;
    		}
    		if(cnt * i > s) break;
    	}
    }

    for(int i = 1 ; i <= s ; i++)
    for(int j = s ; j >= 0 ; j--)
    for(int idx = 0; idx < (int) pre[i].size() ; idx++) {
    	if((idx + 1) * i > j) break;
    	if(maximize(dp[j] , dp[j - (idx + 1) * i] + pre[i][idx]) == true && i == 15) {
    	}
    }
    //for(int i = 1 ; i <= s ; i++) cout << dp[i] << endl;

    cout << dp[s] << endl;

    return 0;
}

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