fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define abdelrahman001 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  3. #define F first
  4. #define S second
  5. #define inFile(t) freopen((t),"r",stdin)
  6. #define outFile(t) freopen((t),"w",stdout)
  7. #define pb push_back
  8. #define pf push_front
  9. #define Pb pop_back
  10. #define all(v) (v).begin(),(v).end()
  11. #define allr(v) (v).rbegin(),(v).rend()
  12. #define Pf pop_front
  13. #define sz size
  14. #define MP make_pair
  15. #define Pc __builtin_popcount
  16. #define pi 2*acos(0)
  17. #define BiEdge(v,a,b,c) (v)[(a)].pb({b,c}),(v)[(b)].pb(({a,c}))
  18. #define mod 998244353
  19. #define point complex<ld>
  20. #define X real()
  21. #define Y imag()
  22. #define pll pair<ll,ll>
  23. #define pii pair<int,int>
  24. #define cross(a,b)(conj(a)*(b)).imag()
  25. #define dot(a,b) (conj(a)*(b)).real()
  26. #define rectangle pair<coordinate,coordinate>
  27. #define line tuple<ll,ll,ll>
  28. #define EPS 1e-7
  29. #define polygon vector<point>
  30. typedef long long ll;
  31. typedef unsigned long long ull;
  32. typedef long double ld;
  33. int const N = 1e3+5,M = 105;
  34. using namespace std;
  35. ll n,m,x,y,arr[N],memo[N][N];
  36. char c;
  37. ll solve(ll ind,ll p,ll h)
  38. {
  39.     if(ind == n)
  40.         return 0;
  41.     ll &ans = memo[ind][h];
  42.     if(p)
  43.         ans = memo[ind][p];
  44.     if(~ans)
  45.         return ans;
  46.     ans = 0;
  47.     if(p)
  48.     {
  49.         if(p<x)
  50.             ans = min(ans,solve(ind+1,p+1,0)+arr[ind]);
  51.         else if(p<y)
  52.             ans = min(ans,min(solve(ind+1,p+1,0)+arr[ind],solve(ind+1,0,h+1)+(n-arr[ind])));
  53.         else
  54.             ans = min(ans,solve(ind+1,0,h+1)+(n-arr[ind]));
  55.     } else
  56.     {
  57.         if(h<x)
  58.             ans = min(ans,solve(ind+1,0,h+1)+(n-arr[ind]));
  59.         else if(h<y)
  60.             ans = min(ans,min(solve(ind+1,p+1,0)+arr[ind],solve(ind+1,0,h+1)+(n-arr[ind])));
  61.         else
  62.             ans = min(ans,solve(ind+1,p+1,0)+(arr[ind]));
  63.     }
  64.     return ans;
  65. }
  66. int main()
  67. {
  68.     abdelrahman001
  69.     cin >> n >> m >> x >> y;
  70.     for(int i =0;i<n;i++)
  71.         for(int j = 0;j<m;j++)
  72.             cin >> c,arr[j]+=(c== '.');
  73.     cout << solve(0,0,0);
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 23136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J2uhth
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!