Advertisement
As932

imagine

Jan 15th, 2021
1,174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <fstream>
  2.  
  3. using namespace std;
  4.  
  5. ifstream cin("imagine.in");
  6. ofstream cout("imagine.out");
  7.  
  8. const int lmax = 255;
  9.  
  10. int l, ans, a[lmax][lmax];
  11.  
  12. void read(){
  13.     cin >> l;
  14.  
  15.     for(int i = 1; i <= l; i++)
  16.         for(int j = 1; j <= l; j++)
  17.             cin >> a[i][j];
  18. }
  19.  
  20. void sum(){
  21.     for(int i = 1; i <= l; i++)
  22.         for(int j = 1; j <= l; j++)
  23.             a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
  24. }
  25.  
  26. void solve(int l1, int l2, int c1, int c2){
  27.     if(l1 == l2 && c1 == c2)
  28.         ans += 2;
  29.     else {
  30.         int sm = a[l2][c2] - a[l1 - 1][c2] - a[l2][c1 - 1] + a[l1 - 1][c1 - 1];
  31.  
  32.         if(sm == 0)
  33.             ans += 2;
  34.         else if(sm == (l2 - l1 + 1) * (c2 - c1 + 1))
  35.             ans += 2;
  36.         else {
  37.             ans += 1;
  38.  
  39.             int mdL = (l1 + l2) / 2;
  40.             int mdC = (c1 + c2) / 2;
  41.  
  42.             solve(mdL + 1, l2, c1, mdC);//A
  43.             solve(l1, mdL, c1, mdC);//B
  44.             solve(mdL + 1, l2, mdC + 1, c2);//C
  45.             solve(l1, mdL, mdC + 1, c2);//D
  46.         }
  47.     }
  48. }
  49.  
  50. int main()
  51. {
  52.     read();
  53.     sum();
  54.     solve(1, l, 1, l);
  55.     cout << ans;
  56.  
  57.     return 0;
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement