oj.uz

Submission #976014

# Submission time Handle Problem Language Result Execution time Memory
976014 2024-05-06T04:59:53 Z vjudge1 Knapsack (NOI18_knapsack) C++17
12 / 100
 3 ms 3420 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

signed main (){
	int s,n; cin >> s >> n;
	pair<int,int> dp[n+1][s+1];
	int w[n+1],h[n+1],k[n+1];
	memset(dp,0,sizeof dp);
	for(int i =1;i<=n;i++){
		cin >> h[i] >> w[i] >> k[i];
	}
	
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=s;j++){
			int tmp = 0,con = 0;
			if(j - w[i] >= 0){
				tmp = dp[i][j-w[i]].fi + h[i];
				con = dp[i][j-w[i]].se + 1;
			}
			
			
			dp[i][j].fi = max(dp[i][j-1].fi,dp[i-1][j].fi);
			if(dp[i][j].fi == dp[i][j-1].fi) dp[i][j].se = dp[i][j-1].se;
			else dp[i][j].se = 0;
			if(con <= k[i]){
				if(max(dp[i][j].fi,tmp) == tmp){
					dp[i][j].fi = tmp;
					dp[i][j].se = con;
				} 
			} else{
				dp[i][j].fi += dp[i-1][j - k[i]*w[i]].fi - dp[i-1][j - k[i]*w[i] - 1].fi;
			}
			
//			cout << dp[i][j].fi << " ";
		}
//		cout << endl;
	}
	cout << dp[n][s].fi << endl;
	
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 3 ms 3420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 3 ms 3420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 3 ms 3420 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 3 ms 3420 KB Output isn't correct
7 Halted 0 ms 0 KB -