fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7.  
  8.  
  9. int n,k,m;
  10.  
  11. int st[300000];
  12. int s[300000];
  13. int e[300000];
  14. int mincost[100009];
  15. ll rating[100009];
  16. ll totalrating = 0;
  17.  
  18.  
  19. void init(int in,int si,int ei){
  20. 	s[in] = si;
  21. 	e[in] = ei;
  22. 	st[in] = 600;
  23. 	if(si!=ei){
  24. 		int middle = (si+ei)/2;
  25. 		init(2*in,si,middle);
  26. 		init(2*in+1,middle+1,ei);
  27. 	}
  28. }
  29.  
  30.  
  31. void update(int in,int si,int ei,int c){
  32. 	if(s[in]==si&&e[in]==ei){if(st[in]>c)st[in] = c;return;}
  33. 	int middle = (s[in] + e[in])/2;
  34.  
  35. 	if(si>middle){update(2*in+1,si,ei,c);}
  36. 	else if(ei<=middle){update(2*in,si,ei,c);}
  37. 	else{
  38. 		update(2*in,si,middle,c);
  39. 		update(2*in+1,middle+1,ei,c);
  40. 	}
  41. }
  42.  
  43.  
  44.  
  45. int query(int ni,int in){
  46. 	if(s[ni]==e[ni])return st[ni];
  47. 	int middle = (s[ni] + e[ni])/2;
  48. 	int mm;
  49. 	if(in<=middle){mm = query(2*ni,in);}
  50. 	else mm = query(2*ni+1,in);
  51. 	return min(mm,st[ni]);
  52. }
  53.  
  54.  
  55.  
  56. vector<pair<ll,int> > V;//cost weight
  57.  
  58.  
  59. ll mc[509][100009];
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68. int main(){
  69. 	freopen("input.txt","r",stdin);
  70. 	int t;
  71. 	cin>>t;
  72. 	while(t--){
  73. 		V.clear();
  74. 		totalrating = 0;
  75. 		cin>>n>>k>>m;
  76. 		init(1,1,n);
  77. 		for(int i=1;i<=n;i++){cin>>rating[i];totalrating += rating[i];}
  78. 		for(int i=0;i<m;i++){
  79. 			int temp,temp2,cost;
  80. 			cin>>temp>>temp2>>cost;
  81. 			update(1,temp,temp2,cost);
  82. 		}
  83. 		for(int i=1;i<=n;i++){
  84. 		if(rating[i]<0){
  85. 			mincost[i] = query(1,i);
  86. 		if(mincost[i]<=k){V.push_back(make_pair(-rating[i],mincost[i]));}}
  87. 		}
  88. 		for(int i=0;i<(int)V.size();i++){cout<<V[i].first<<' '<<V[i].second<<endl;}
  89.  
  90. 		int vl = V.size();
  91. 		ll w = V[0].second;
  92.  
  93. 		for(int i=0;i<w&&i<=k;i++){mc[i][0]=0;}
  94. 		for(int i=w;i<=k;i++)mc[i][0]=V[0].first;
  95. 		for(int i=0;i<=vl;i++)mc[0][vl]=0;
  96. 		for(int i=1;i<=k;i++){
  97. 			for(int j=1;j<vl;j++){
  98. 				mc[i][j] = mc[i][j-1];
  99. 				if(i-V[i].second>0&&mc[i-V[j].second][j-1]>mc[i][j])
  100. 					m[i][j] = mc[i-V[j].second][j-1];
  101. 			}
  102. 		}
  103.  
  104. 		cout<<mc[k][vl]<<endl;
  105.  
  106.  
  107.  
  108.  
  109. 	}
  110. }
  111.  
Compilation error #stdin compilation error #stdout 0s 0KB
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
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:100:9: error: invalid types 'int[int]' for array subscript
      m[i][j] = mc[i-V[j].second][j-1];
         ^
stdout
copy 
Standard output is empty
https://ideone.com/5p0t9R
language:
C++14 (gcc 8.3)
created:
8 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!