fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. using namespace std;
  5.  
  6. struct Query{
  7. 	int type;
  8. 	int i , w , v;
  9. 	int W;
  10. };
  11. struct Item{
  12. 	int number , weight , value;
  13. };
  14.  
  15. #define INF (1<<28)
  16.  
  17. #define iMax (3000)
  18. #define wMax (10000)
  19. #define qMax (300)
  20. Item item[iMax];
  21. int position[iMax];
  22. Query query[qMax];
  23. bool important[iMax];
  24.  
  25. int dp[iMax+1][wMax+1];
  26.  
  27.  
  28. bool is_important(const Item &a,const Item &b){ return important[a.number] < important[b.number]; }
  29.  
  30. int main(){
  31. 	int N,Q,C=0;
  32. 	cin >> N >> Q;
  33. 	for(int i = 0 ; i < N ; i++){
  34. 		item[i].number = i;
  35. 		cin >> item[i].weight >> item[i].value;
  36. 	}
  37.  
  38. 	for(int i = 0 ; i < Q ; i++){
  39. 		cin >> query[i].type;
  40. 		if(query[i].type == 0){
  41. 			cin >> query[i].W;
  42. 		}else{
  43. 			cin >> query[i].i >> query[i].w >> query[i].v;
  44. 			important[--query[i].i] = true;
  45. 		}
  46. 	}
  47. 	C = count(important,important+N,true); 
  48. 	sort(item,item+N,is_important);
  49. 	for(int i = 0 ; i < N ; i++) position[item[i].number] = i;
  50.  
  51. 	for(int i = 0 ; i <= N ; i++) for(int j = 0 ; j <= wMax ; j++) dp[i][j] = -INF;
  52. 	dp[0][0] = 0;
  53. 	for(int i = 0 ; i < N ; i++){
  54. 		for(int j = 0 ; j <= wMax ; j++){
  55. 			dp[i+1][j] = dp[i][j];
  56. 			if(j) dp[i+1][j] = max(dp[i+1][j],dp[i+1][j-1]);
  57. 			if(j-item[i].weight >= 0){
  58. 				dp[i+1][j] = max(dp[i+1][j],dp[i][j-item[i].weight]+item[i].value);
  59. 			}
  60. 		}
  61. 	}
  62. 	for(int q = 0 ; q < Q ; q++){
  63. 		if(query[q].type == 0) cout << dp[N][query[q].W] << endl;
  64. 		else{
  65. 			item[position[query[q].i]].weight = query[q].w ; 
  66. 			item[position[query[q].i]].value  = query[q].v ;
  67. 			for(int i = N-C ; i < N ; i++){
  68. 				for(int j = 0 ; j <= wMax ; j++){
  69. 					dp[i+1][j] = dp[i][j];
  70. 					if(j) dp[i+1][j] = max(dp[i+1][j],dp[i+1][j-1]);
  71. 					if(j-item[i].weight >= 0){
  72. 						dp[i+1][j] = max(dp[i+1][j],dp[i][j-item[i].weight]+item[i].value);
  73. 					}
  74. 				}
  75. 			}
  76. 		}
  77. 	}
  78.  
  79. }
Runtime error #stdin #stdout 0.4s 120000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XOVsz
language:
C++ (gcc 8.3)
created:
12 years 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!