Advertisement
Guest User

Untitled

a guest
Nov 11th, 2019
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define eb emplace_back
  6. #define mp make_pair
  7. #define mt make_tuple
  8. #define ms(arr, val) memset(arr, val, sizeof(arr))
  9.  
  10. #define N 100000
  11. #define R 51
  12. #define INF (int)100000
  13.  
  14. int n, k, g1, g2, g3, s; string str;
  15. int dp[R];
  16.  
  17. int f(int i, int j)
  18. {
  19.     if(i >= n && j == 0)
  20.     {
  21.         return 0;
  22.     }
  23.     else if(i >= n && j != 0)
  24.     {
  25.         return -INF;
  26.     }
  27.     else if(i + 2 < n && str[i] == '.' && str[i + 1] == '#' && str[i + 2] == '.')
  28.     {
  29.         return max(f(i + 3, j - 1), f(i + 2, j));
  30.     }
  31.     else if(i + 1 < n && str[i] == '.' && str[i + 1] == '.')
  32.     {
  33.         return max(1 + f(i + 2, j), f(i + 1, j));
  34.     }
  35.     else
  36.     {
  37.         return f(i + 1, j);
  38.     }
  39. }
  40.  
  41. int main()
  42. {
  43.     if(fopen("input_muntu.in", "r"))
  44.     {
  45.         freopen("input_muntu.in", "r", stdin);
  46.         freopen("output_muntu.out", "w", stdout);
  47.     }
  48.    
  49.     ms(dp, 0); s = 0;
  50.     cin >> n >> k >> g1 >> g2 >> g3 >> str;
  51.     for(char ch : str) if(ch == '.') s++;
  52.  
  53.     long long ans = 0, t1, t2, t3;
  54.     for(int i = 0; i < R; i++)
  55.     {
  56.         dp[i] = f(0, i);
  57.         if(dp[i] * g2 + i * g3 > ans)
  58.         {
  59.             ans = dp[i] * g2 + i * g3;
  60.             t2 = dp[i]; t3 = i;
  61.         }
  62.     }
  63.  
  64.     t1 = s - (t2 + t3) * 2;
  65.     k = k - t1;
  66.  
  67.     if(k < 0)
  68.     {
  69.         t1 = t1 + k;
  70.         k = 0;
  71.     }
  72.  
  73.     if(g2 > g3)
  74.     {
  75.         swap(g2, g3);
  76.         swap(t2, t3);
  77.     }
  78.  
  79.     while(k > 0)
  80.     {
  81.         if(g1 > g2 && t2 > 0)
  82.         {
  83.             t1 = t1 + 2;
  84.             t2 = t2 - 1;
  85.  
  86.             if(k > 1) k--;
  87.             else t1--;
  88.         }
  89.         else if(g1 > g3 && t3 > 0)
  90.         {
  91.             t1 = t1 + 2;
  92.             t3 = t3 - 1;
  93.  
  94.             if(k > 1) k--;
  95.             else t1--;
  96.         }
  97.         else if(g1 * 2 > g2 && t2 > 0 && k > 1)
  98.         {
  99.             t1 = t1 + 2;
  100.             t2 = t2 - 1;
  101.             k--;
  102.         }
  103.         else if(g1 * 2 > g3 && t3 > 0 && k > 1)
  104.         {
  105.             t1 = t1 + 2;
  106.             t3 = t3 - 1;
  107.             k--;
  108.         }
  109.         k--;
  110.     }
  111.  
  112.     ans = t1 * g1 + t2 * g2 + t3 * g3;
  113.     cout << ans << endl;
  114.  
  115.     return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement