oj.uz

답안 #433009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433009 2021-06-18T17:32:58 Z Autron Knapsack (NOI18_knapsack) C++14
12 / 100
 3 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

int s, n;
vector<int> v, w, k;
/*
thonking pad

dp[j]=max(dp[j], dp[j-w[i]*nr]+v[i]*nr), it jumps from w[i] to w[i]
you only need the last k[i], dp's wiht v[is added acordingly;
each step you add 
deque, old ones, get poped, new one gets pushed it get compared with good comp
thatn best is taken
lmao

*/

int32_t main(){
	cin>>s>>n;
	v.resize(n+1);
	w.resize(n+1);
	k.resize(n+1);
	for(int i=1;i<=n;++i) cin>>v[i]>>w[i]>>k[i];
	vector<vector<int>> dp(2, vector<int>(s+1, -1e18));
	dp[0][0]=0;
	for(int i=1;i<=n;++i){
		int l=i%2, nl=1-l;
		for(int j=0;j<w[i]&&(j+w[i]<=s);j++){
			deque<int> dq;
			dq.push_back(0);
			dp[l][j]=max(dp[l][j], dp[nl][j]);
			for(int j2=1;j+j2*w[i]<=s;j2++){
				if(!dq.empty()&&(j2-dq.back()>k[i])) dq.pop_back();
				while((!dq.empty())&&(dp[nl][j+j2*w[i]]>(dp[nl][j+dq.front()*w[i]]+(j2-dq.front())*v[i]))) dq.pop_front();
				dq.push_front(j2);
				dp[l][j+j2*w[i]]=dp[nl][j+dq.back()*w[i]]+(j2-dq.back())*v[i];
			}
		}
	}
	int sol=0;
	for(int j=0;j<=s;++j) sol=max(sol, dp[n%2][j]);
	cout<<sol<<"\n";
	return 0;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 27.0

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