Submission #1023669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023669		vjudge1	Knapsack (NOI18_knapsack)	C++98	0 / 100	0 ms	348 KiB

knapsack

#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <bits/stdc++.h>
#include <map>
#include <deque>
#define int long long
using namespace std;
int INF = 1e9;
signed main(){
/*	ifstream cin("sleepy.in");
	ofstream cout("sleepy.out");*/
	int n , m;
	cin >> m >> n;
	int a[n] , b[n];
	int sum = 0 , sum1 = 0 , c[n];
	vector < int > v(m + 1);
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i] >> c[i];
		sum += a[i]; sum1 += b[i];
	}
	if(sum <= m){
		cout << sum1;
		return 0;
	}
	vector <int> dp(m + 1, 0);
	for(int i = 0; i < n; i++){
		if(dp[a[i]] == 0){
			dp[a[i]] = b[i];
			v[a[i]] = i;
		}
			
		else {
			dp[a[i] * 2] = b[i];
			v[a[i] * 2] = i;
		}
		
	} 
	for(int i = 0; i <= m; i++){
		if(dp[i] != 0){
			for(int j = 0; j < n; j++){
				if(v[i] != j){
					if(dp[i + a[j]] <= dp[i] + b[j] and i + a[j] <= m){
						dp[i + a[j]] = dp[i] + b[j];
						v[i + a[j]] = j;
				
					}
				}
			}
		}
	}
	int mx = 0;
	for(int i = 0; i <= m; i++) mx = max(mx , dp[i]);
	cout  << mx;
	return 0; 
	
}
//AZIM_BEST

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