fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <cstdio>
  6. using namespace std;
  7.  
  8. long long knap[100000+1][500+1];
  9.  
  10. struct oper {
  11. 	int l,r,cost;
  12. };
  13.  
  14. int main() {
  15. 	int n,k,m,t;
  16. //	freopen("codechef_MChef.txt","r",stdin);
  17. 	cin >> t;
  18. 	while(t--){
  19. 		cin >> n >> k >> m;
  20. 		vector<long long> v;
  21. 		map<int,long long> mymap;
  22. 		long long a[n];
  23. 		vector<long long> b(n,1<<30);//[n] = {1<<31};
  24. 		int sz=0;
  25. 		long long sum=0;
  26. 		for(int i=0;i<n;i++){
  27. 			cin >>a[i];
  28. 			sum+=a[i];
  29. 			if(a[i]<0){
  30. 				mymap[i] = a[i];
  31. 				v.push_back(-1*a[i]);
  32. 				sz++;
  33. 			}
  34. 				//v.push_back(a[i]);
  35. 		}
  36. 		vector<long long> wt;
  37. 		//vector<int> L(n),R(n);
  38. 		//vector<vector <int> > L(n),R(n);
  39. 		vector<int> L[n],R[n];
  40. 		vector<oper> operarray;
  41. 		vector<int> cost;
  42. 		for(int i=0;i<m;i++){
  43. 			int j,k,val;
  44. 			cin >> j >> k >> val;
  45. 			L[j-1].push_back(i);
  46. 			R[k-1].push_back(i);
  47. 			struct oper opertemp;
  48. 			opertemp.l=j;
  49. 			opertemp.r=k;
  50. 			opertemp.cost=val;
  51. 			operarray.push_back(opertemp);
  52. 			cost.push_back(val);
  53. 		}
  54.         //cout << "hiii" << endl;
  55. 		set<pair<int,int> > iset;
  56. 		for(int i=0;i<n;i++){
  57. 			for(int j=0;j<L[i].size();j++){
  58. 				int index = L[i][j];
  59. 			//	cout << "index " <<index << " for " << i << endl;
  60. 				//iset.insert(make_pair(operarray[index].cost,index));
  61. 				iset.insert(make_pair(cost[index],index));
  62. 			//	cout << "inserted " << index << " " << operarray[index].cost << endl;
  63. 			//	cout << "iset size " << iset.size() << endl;
  64. 			//	for(set<pair<int,int>,classcomp> :: iterator it = iset.begin();it!=iset.end();it++){
  65.             //        cout << it->first << " " << it->second << endl;
  66. 			//	}
  67. 			}
  68. 			b[i] = iset.begin()->first;
  69. 			//cout << "assigning " <<i << " "<< b[i] << endl;
  70. 			for(int j=0;j<R[i].size();j++){
  71. 				int index = R[i][j];
  72. 				//iset.erase(make_pair(operarray[index].cost,index));
  73. 				iset.erase(make_pair(cost[index],index));
  74. 				//cout << "deleted " << index << " " << operarray[index].cost << endl;
  75. 			}
  76. 		}
  77. 		for(map<int,long long>:: iterator it=mymap.begin();it!=mymap.end();it++){
  78. 			//cout << it->first << " " << b[it->first] << endl;
  79. 			wt.push_back(b[it->first]);
  80. 		}
  81. 	//	for(int i=0;i<sz;i++){
  82. 	//		cout << v[i] << " " << wt[i] << endl;
  83. 	//	}
  84. 		//long long knap[sz+1][k+1];
  85. 		for(int i=0;i<=sz;i++){
  86. 			for(int w=0;w<=k;w++){
  87. 				if(i==0||w==0)
  88. 					knap[i][w]=0;
  89. 				else if(wt[i-1]<=w){
  90. 					knap[i][w] = max(v[i-1]+knap[i-1][w-wt[i-1]],knap[i-1][w]);
  91. 		//			cout << "knap " << i << " " << w << " is " << max(v[i-1]+knap[i-1][w-wt[i-1]],knap[i-1][w]) << " max of " <<v[i-1] << " + "<< "knap["<<i-1<<"]["<<w-wt[i-1]<<"] "<< knap[i-1][w-wt[i-1]] << " or " << knap[i-1][w]<< endl;
  92. 				}
  93. 				else{
  94. 					knap[i][w] = knap[i-1][w];
  95. 					//cout << "else knap " << i << " " << w << knap[i][w] << endl;
  96. 				}
  97. 			}
  98. 		}
  99. 		cout << sum+knap[sz][k]<< endl;
  100. 	}
  101. 	return 0;
  102. }
  103.  
Success #stdin #stdout 0s 394688KB
comments ()
stdin
copy 
1 5 10 5
-10 2 5 -7 -10
1 1 5
2 4 10
4 4 12
3 4 10
1 5 15
stdout
copy 
-10
https://ideone.com/SsbABr
language:
C++ (gcc 8.3)
created:
9 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!