Submission #817420

#	Time	Username	Problem	Language	Result	Execution time	Memory
817420		mariam197	Knapsack (NOI18_knapsack)	C++17	100 / 100	90 ms	19668 KiB

knapsack

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
#define ll long long
#define ld long double
#define mod 1000000007
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
vector<pair<int,int> > arr[2001];
bool compare (pair <int, int> a, pair <int, int> b) {
	return a.first > b.first;
}
int dp[2001][2001];
int solve(int i,int rem){
    if(i==0 || rem==0) return 0;
    if(dp[i][rem]!=-1) return dp[i][rem];
	int ans = solve(i-1,rem);
	int sum=0,w=0;
	for (auto j : arr[i]) {
		int val = j.first,k=j.second;
		while (k--) {
			sum += val;
			w += i;
			if (w > rem) {
				return dp[i][rem] = ans;
			}
			ans = max(ans, sum + solve(i - 1, rem - w));
		}
	}
	return dp[i][rem] = ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int s,n;
    cin>>s>>n;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		arr[b].push_back({a,c});
	}
	for(int i = 1; i <= 2000; i++) {
		sort(arr[i].begin(),arr[i].end(),compare);
	}
	cout<<solve(2000,s);
    return 0;
}

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