fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. #define oo 1e9
  16. const int N = 1e5 + 5;
  17. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // log(n) __gcd(a,b)
  18. //todo اى ويل بريبير ماى بيبرز تو بى ذا بيست ان زيس وورلد
  19. int n,m,x,y;
  20. vector<vector<char>>v;
  21. vector<pair<int,int>> col;
  22. int dp[1003][1003][3];
  23. int solve(int i,int j,int s)
  24. {
  25.     if(i==m) return 0;
  26.     int& ret=dp[i][j][s];
  27.     if(ret!=-1) return ret;
  28.     int w=1e9,b=1e9;
  29.     if(i==0)
  30.     {
  31.      w=solve(i+1,1,0)+col[i].first;
  32.      b=solve(i+1,1,1)+col[i].second;
  33.     }
  34.     else
  35.     {
  36.       if(s==0)
  37.       {
  38.         if(j<x) w=solve(i+1,j+1,0)+col[i].first;
  39.         else if(j>=x&&j<y) { b=solve(i+1,1,1)+col[i].second; w=solve(i+1,j+1,0)+col[i].first; }
  40.         else if(j>=y) b=solve(i+1,1,1)+col[i].second;
  41.  
  42.       }
  43.       else 
  44.       {
  45.         if(j<x) b=solve(i+1,j+1,1)+col[i].second;
  46.         else if(j>=x&&j<y) {  b=solve(i+1,j+1,1)+col[i].second; w=solve(i+1,1,0)+col[i].first; }
  47.         else if(j>=y) w=solve(i+1,1,0)+col[i].first;
  48.       }
  49.     }
  50.     return ret = min(w,b);
  51. }
  52. void HereWeGoAgain()
  53. {
  54.    cin>>n>>m>>x>>y;
  55.    v.resize(n);
  56.    for(int i=0;i<n;i++)
  57.    v[i].resize(m);
  58.    for(int i=0;i<n;i++)
  59.     for(int j=0;j<m;j++)
  60.     cin>>v[i][j];
  61.    for(int i=0;i<m;i++)
  62.    { 
  63.     int w=0,b=0;
  64.     for(int j=0;j<n;j++)
  65.     {
  66.         if(v[j][i]=='#') b++;
  67.         else w++;
  68.     }
  69.     col.push_back({w,b});
  70.    }
  71.    dpp(dp,-1);
  72.    //for(int i=0;i<col.size();i++) cout<<col[i].first<<' '<<col[i].second<<el;
  73.    cout<<solve(0,0,0);
  74. }
  75. int32_t main() 
  76. {
  77.     Arwa
  78.     int t=1;
  79.     //cin>>t;
  80.     for(int i=1;i<=t;i++)
  81.     {
  82.     HereWeGoAgain();
  83.     }
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 27044KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/LbQIDI
language:
C++ (gcc 8.3)
created:
2 days 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!