Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define eb emplace_back
- #define mp make_pair
- #define mt make_tuple
- #define ms(arr, val) memset(arr, val, sizeof(arr))
- #define N 100000
- #define R 51
- #define INF (int)100000
- int n, k, g1, g2, g3, s; string str;
- int dp[R];
- int f(int i, int j)
- {
- if(i >= n && j == 0)
- {
- return 0;
- }
- else if(i >= n && j != 0)
- {
- return -INF;
- }
- else if(i + 2 < n && str[i] == '.' && str[i + 1] == '#' && str[i + 2] == '.')
- {
- return max(f(i + 3, j - 1), f(i + 2, j));
- }
- else if(i + 1 < n && str[i] == '.' && str[i + 1] == '.')
- {
- return max(1 + f(i + 2, j), f(i + 1, j));
- }
- else
- {
- return f(i + 1, j);
- }
- }
- int main()
- {
- if(fopen("input_muntu.in", "r"))
- {
- freopen("input_muntu.in", "r", stdin);
- freopen("output_muntu.out", "w", stdout);
- }
- ms(dp, 0); s = 0;
- cin >> n >> k >> g1 >> g2 >> g3 >> str;
- for(char ch : str) if(ch == '.') s++;
- long long ans = 0, t1, t2, t3;
- for(int i = 0; i < R; i++)
- {
- dp[i] = f(0, i);
- if(dp[i] * g2 + i * g3 > ans)
- {
- ans = dp[i] * g2 + i * g3;
- t2 = dp[i]; t3 = i;
- }
- }
- t1 = s - (t2 + t3) * 2;
- k = k - t1;
- if(k < 0)
- {
- t1 = t1 + k;
- k = 0;
- }
- if(g2 > g3)
- {
- swap(g2, g3);
- swap(t2, t3);
- }
- while(k > 0)
- {
- if(g1 > g2 && t2 > 0)
- {
- t1 = t1 + 2;
- t2 = t2 - 1;
- if(k > 1) k--;
- else t1--;
- }
- else if(g1 > g3 && t3 > 0)
- {
- t1 = t1 + 2;
- t3 = t3 - 1;
- if(k > 1) k--;
- else t1--;
- }
- else if(g1 * 2 > g2 && t2 > 0 && k > 1)
- {
- t1 = t1 + 2;
- t2 = t2 - 1;
- k--;
- }
- else if(g1 * 2 > g3 && t3 > 0 && k > 1)
- {
- t1 = t1 + 2;
- t3 = t3 - 1;
- k--;
- }
- k--;
- }
- ans = t1 * g1 + t2 * g2 + t3 * g3;
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement