oj.uz

답안 #464834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
464834 2021-08-14T09:52:13 Z Qw3rTy Knapsack (NOI18_knapsack) C++11
17 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#define int long long
#define pi pair<int,int>
#define fi first
#define se second
using namespace std;

const int maxN = 1e5+5;
const int maxV = 2e3+5;
int cnt = 0;
pi item[maxN*40]; //.fi = value; .se = weight;
int f[maxV];
int S,N;

bool cmp(pi a, pi b){
	return a.se > b.se;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("../test.in","r",stdin);
	cin >> S >> N;
	for(int i = 1; i <= N; ++i){
		int v,w,k; cin >> v >> w >> k;
		int j = 1;
		while(j <= k){
			if(w * j > S)break;
			item[++cnt] = pi(v*j,w*j);
			j = j * 2;
		}
	}
	sort(item+1,item+cnt+1,cmp);
	for(int i = 1; i <= cnt; ++i){
		for(int j = S; j >= item[i].se; --j){
			f[j] = max(f[j], f[j-item[i].se] + item[i].fi);
		}
	}
	cout << f[S] << '\n';
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -