fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef unsigned long long ull;
  7.  
  8. const int P = 55;
  9. const int N = 100005;
  10. const int inf = 1e9;
  11.  
  12. int dp[P][N][2], mx[2][N];
  13. int n, k, m, g1, g2, g3, a[P];
  14.  
  15. int main(){
  16. 	ios::sync_with_stdio(false);
  17. 	cin.tie(NULL);
  18. 	cout.tie(NULL);
  19. 	cout<<setprecision(32);
  20.  
  21. 	cin>>n>>k>>g1>>g2>>g3;
  22. 	string str; cin>>str;
  23. 	memset(a, 0, sizeof(a));
  24. 	m = 1;
  25. 	for(int i = 0; i < n; i++){
  26. 		if(str[i] == '#')m++;
  27. 		else a[m]++;
  28. 	}
  29. 	memset(dp, 0, sizeof(dp));
  30. 	for(int j = 0; j <= k; j++){
  31. 		dp[0][j][1] = -inf;
  32. 	}
  33. 	for(int i = 1; i <= m; i++){
  34. 		if(a[i] == 0){
  35. 			for(int j = 0; j <= k; j++){
  36. 				dp[i][j][0] = dp[i - 1][j][0];
  37. 				dp[i][j][1] = -inf;
  38.  			}
  39.  			continue;
  40. 		}
  41. 		for(int j = 0; j <= k; j++){
  42. 			dp[i][j][0] = dp[i][j][1] = -inf;
  43. 			mx[0][j] = dp[i - 1][j][0] - j*g1 + ((a[i] + j)/2)*g2;
  44. 			mx[1][j] = dp[i - 1][j][0] - j*g1 + ((a[i] + j - 1)/2)*g2;
  45. 		}
  46. 		deque<int> dq[2];
  47. 		for(int j = 0; j <= k; j++){
  48. 			for(int par = 0; par < 2; par++){
  49. 				if(!dq[par].empty() && dq[par].front() < j - a[i])dq[par].pop_front();
  50. 				while(!dq[par].empty() && mx[par][dq[par].back()] <= mx[par][j])dq[par].pop_back();
  51. 				dq[par].push_back(j);
  52. 			}
  53. 			dp[i][j][0] = max(dp[i][j][0], mx[j&1][dq[j&1].front()] + j*g1 - (j/2)*g2);
  54. 		}
  55. 		for(int par = 0; par < 2; par++){
  56. 			dq[par].clear();
  57. 		}
  58. 		for(int j = 0; j <= k; j++){
  59. 			mx[0][j] = dp[i - 1][j][1] + g3 - j*g1 + ((a[i] + j - 1)/2)*g2;
  60. 			mx[1][j] = dp[i - 1][j][1] + g3 - j*g1 + ((a[i] + j)/2)*g2 - g2;
  61. 		}
  62. 		for(int j = 0; j <= k; j++){
  63. 			for(int par = 0; par < 2; par++){
  64. 				if(!dq[par].empty() && dq[par].front() < j - a[i] + 1)dq[par].pop_front();
  65. 				while(!dq[par].empty() && mx[par][dq[par].back()] <= mx[par][j])dq[par].pop_back();
  66. 				dq[par].push_back(j);
  67. 			}
  68. 			dp[i][j][0] = max(dp[i][j][0], mx[j&1][dq[j&1].front()] + j*g1 - (j/2)*g2);
  69. 		}
  70. 		for(int par = 0; par < 2; par++){
  71. 			dq[par].clear();
  72. 		}
  73. 		for(int j = 0; j <= k; j++){
  74. 			mx[0][j] = dp[i - 1][j][0] - j*g1 + ((a[i] + j - 1)/2)*g2;
  75. 			mx[1][j] = dp[i - 1][j][0] - j*g1 + ((a[i] + j)/2)*g2 - g2;
  76. 		}
  77. 		for(int j = 0; j <= k; j++){
  78. 			for(int par = 0; par < 2; par++){
  79. 				if(!dq[par].empty() && dq[par].front() < j - a[i] + 1)dq[par].pop_front();
  80. 				while(!dq[par].empty() && mx[par][dq[par].back()] <= mx[par][j])dq[par].pop_back();
  81. 				dq[par].push_back(j);
  82. 			}
  83. 			dp[i][j][1] = max(dp[i][j][1], mx[j&1][dq[j&1].front()] + j*g1 - (j/2)*g2);
  84. 		}
  85. 		if(a[i] == 1)continue;
  86. 		for(int par = 0; par < 2; par++){
  87. 			dq[par].clear();
  88. 		}
  89. 		for(int j = 0; j <= k; j++){
  90. 			mx[0][j] = dp[i - 1][j][1] + g3 - j*g1 + ((a[i] + j)/2)*g2 - g2;
  91. 			mx[1][j] = dp[i - 1][j][1] + g3 - j*g1 + ((a[i] + j - 1)/2)*g2 - g2;
  92. 		}
  93. 		for(int j = 0; j <= k; j++){
  94. 			for(int par = 0; par < 2; par++){
  95. 				if(!dq[par].empty() && dq[par].front() < j - a[i] + 2)dq[par].pop_front();
  96. 				while(!dq[par].empty() && mx[par][dq[par].back()] <= mx[par][j])dq[par].pop_back();
  97. 				dq[par].push_back(j);
  98. 			}
  99. 			dp[i][j][1] = max(dp[i][j][1], mx[j&1][dq[j&1].front()] + j*g1 - (j/2)*g2);
  100. 		}
  101. 	}
  102. 	cout<<dp[m][k][0]<<'\n';
  103.  
  104. 	return 0;
  105. }
Success #stdin #stdout 0.01s 46488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/4wVPKI
language:
C++14 (gcc 8.3)
created:
4 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!