fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define bit(mask, i) ((mask >> i) & 1)
  6. #define BIT(n) (1ll << n)
  7.  
  8. using namespace std;
  9.  
  10. const int maxn = 5e2;
  11.  
  12. struct rectangle
  13. {
  14.     int up, right, down, left;
  15.     bool isnll()
  16.     {
  17.         return (up == -1 && right == -1 && left == -1 && down == -1);
  18.     }
  19.     void printRect()
  20.     {
  21.         cout << up << ' ' << right << ' ' << down << ' ' << left, el;
  22.     }
  23. };
  24.  
  25. int n, k, r, p;
  26. ll a[maxn + 10][maxn + 10], pre[maxn + 10][maxn + 10], ans = 0;
  27. const rectangle nllRect = {-1, -1, -1, -1};
  28.  
  29. rectangle intersect(rectangle a, rectangle b)
  30. {
  31.     rectangle ans;
  32.     ans.left = max(a.left, b.left);
  33.     ans.right = min(a.right, b.right);
  34.     ans.up = max(a.up, b.up);
  35.     ans.down = min(a.down, b.down);
  36.     return ans;
  37. }
  38. ll acreage(rectangle a)
  39. {
  40.     ll up = a.up;
  41.     ll down = a.down;
  42.     ll right = a.right;
  43.     ll left = a.left;
  44.     if (up > down || right < left) return 0;
  45.     return pre[right][down] - pre[right][up - 1] - pre[left - 1][down] + pre[left - 1][up - 1];
  46. }
  47.  
  48. int main()
  49. {
  50.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  51.     if (fopen("BONUS.INP", "r"))
  52.     {
  53.         freopen("BONUS.INP", "r", stdin);
  54.         freopen("BONUS.OUT", "w", stdout);
  55.     }
  56.  
  57.     cin >> n >> k >> r >> p;
  58.     for (int i = 1; i <= n; i++)
  59.     {
  60.         for (int j = 1; j <= n; j++)
  61.         {
  62.             cin >> a[i][j];
  63.             pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
  64.         }
  65.     }
  66.     while (k--)
  67.     {
  68.         vector<rectangle> v;
  69.         for (int i = 1; i <= p; i++)
  70.         {
  71.             int l, u;
  72.             cin >> l >> u;
  73.             v.push_back({u, l + r - 1, u + r - 1, l});
  74.         }
  75.         ll s = 0;
  76.         for (int mask = 1; mask < BIT(p); mask++)
  77.         {
  78.             rectangle t = nllRect;
  79.             for (int i = 0; i < p; i++)
  80.             {
  81.                 if (!bit(mask, i)) continue;
  82.                 if (t.isnll()) t = v[i];
  83.                 else t = intersect(t, v[i]);
  84.             }
  85.             if (__builtin_popcount(mask) & 1) s += acreage(t);
  86.             else s -= acreage(t);
  87.         }
  88.         ans = max(ans, s);
  89.     }
  90.     cout << ans;
  91. }
  92.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/O91Rlg
language:
C++14 (gcc 8.3)
created:
25 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!