oj.uz

Submission #639820

# Submission time Handle Problem Language Result Execution time Memory
639820 2022-09-11T22:28:53 Z oseip Knapsack (NOI18_knapsack) C++17
0 / 100
 1 ms 596 KB 
// Source: https://usaco.guide/general/io

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

struct item{
	int V; //Value
	int W; //Weight
	int K; //Kuantity
};

int S, N, x, iten; //size, number of items
vector<pair<int,int>> items;  
vector<int> ans;
vector<int> kays;

int main() {
	cin >> S >> N;
	S++;
	items.resize(N); ans.resize(S); kays.resize(N);
	for (int i = 0; i < N; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		items[i].first = x; items[i].second = y; kays[i] = z;
	}
	vector<vector<int>> keys(S);
	for (int i = 0 ; i < S; i++) {
		for (int j = 0; j < N; j++) {
			keys[i].push_back(kays[j]);
		}
	}
	for (int i = 0; i < S; i++) {
		int x = 0; iten = -1;
		for (int j = 0; j < N; j++) {
			if (items[j].second > i) continue;
			if (keys[i-items[j].second][j] > 0) {
				x = max(x,ans[i-items[j].second] + items[j].first); 
				if (x == ans[i-items[j].second] + items[j].first) iten = j;
			}
		}
		keys[i] = keys[i-items[iten].second]; keys[i][iten]--;
		ans[i] = x;	
	}
	x = 0;
	for (int i : ans) {
		x = max(x,i);
	}
	cout << x << endl;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 428 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 428 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -