fork download
copy 
  1. #include<bits/stdc++.h>
  2. const int N=1e4+5; 
  3. using namespace std;
  4. int m,n;
  5. int p[N];
  6. int c[N];
  7. int dp[N][N];
  8. int Trace[N][N];
  9. vector<int>t;
  10.  
  11. void sol(){
  12.   memset(dp,-0x3f,sizeof dp);
  13.   dp[0][0]=0;
  14.   for(int i=1;i<=n;i++){
  15. 	 for(int j=0;j<=m;j++){
  16. 		dp[i][j]=dp[i-1][j];
  17. 		 if(j>=c[i]){
  18. 			dp[i][j]=max(dp[i][j],dp[i-1][j-c[i]]+p[i]);
  19. 		 }
  20. 	 }
  21.  }
  22.  int ans=0;
  23.  int j_toi_uu;
  24.  for(int j=0;j<=m;j++){
  25.  	 ans=max(ans,dp[n][j]);
  26. 	 if(ans==dp[n][j]){
  27. 		j_toi_uu=j;
  28. 	 }
  29.  }
  30.  cout << ans << '\n';
  31.  int i=n,j=j_toi_uu;
  32.  while(i > 0){
  33. 	if(dp[i][j]==dp[i-1][j])i--;
  34. 	else{
  35. 		cout << i << ' ';
  36. 		i--;
  37. 		j-=c[i];
  38. 	 }
  39.  }
  40.  cout << '\n';
  41.  cout<<j_toi_uu<<"\n";
  42.  //return 0;
  43. }
  44.  
  45. main(){
  46.   cin>>n>>m; 
  47.   for(int i=1;i<=n;i++){
  48.     cin>>c[i]>>p[i]; 
  49.   }
  50.   sol(); 
  51.   return 0; 
  52. }
Success #stdin #stdout 0.06s 395080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0

0
https://ideone.com/jub8Dd
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!