Submission #3381518

---

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;

int N,P,a,B[5010];
pair<int,int> A[5010];
int dp[5010][5200] = {{0}};
int main(){
	cin >> N >> P;
	for(int i=1;i<=N;i++){
		cin >> a >> B[i];
		A[i] = {a,i};
	}
	sort(A+1,A+N+1);
	reverse(A+1,A+N+1);
	int ans = 0;
	for(int i=1;i<=N;i++){
		int k = A[i].second;
		int p = A[i].first;
		for(int j=1;j<=P+p;j++){
			if(j-p>=0) dp[i][j] = max(dp[i-1][j-p] + B[k],dp[i-1][j]);
			else dp[i][j] = dp[i-1][j];
			ans = max(ans,dp[i][j]);
		}
	}
	cout << ans << endl;
}

Submission Info

Judge Result