fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e3;
  5. int n, k, r, p;
  6. long long ans;
  7. long long a[N][N];
  8.  
  9. struct rect {
  10.     int x1, x2, y1, y2;
  11.     rect(int u, int v, int x, int y) {
  12.         x1=u; y1=v; x2=x; y2=y;
  13.     }
  14. };
  15.  
  16. rect intersect(rect u, rect v) {
  17.     rect ans = rect(1, 1, n, n);
  18.     ans.x1 = max(u.x1, v.x1);
  19.     ans.x2 = min(u.x2, v.x2);
  20.     ans.y1 = max(u.y1, v.y1);
  21.     ans.y2 = min(u.y2, v.y2);
  22.     return ans;
  23. }
  24.  
  25. long long get(rect u) {
  26.     if (u.x2 < u.x1 || u.y2 < u.y1) return 0;
  27.     return a[u.x2][u.y2]-a[u.x2][u.y1-1]-a[u.x1-1][u.y2]+a[u.x1-1][u.y1-1];
  28. }
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  32.     cin >> n >> k >> r >> p;
  33.     for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
  34.         cin >> a[i][j];
  35.         a[i][j] += a[i][j-1]+a[i-1][j]-a[i-1][j-1];
  36.     }
  37.  
  38.     ans = -1e9;
  39.     for (int i = 1; i <= k; i++) {
  40.         long long sum = 0;
  41.         vector<rect> rs;
  42.         for (int i = 1; i <= p; i++) {
  43.             int x, y; cin >> x >> y;
  44.             rs.push_back(rect(x, y, x+r-1, y+r-1));
  45.         }
  46.         for (int i = 1; i < (1 << p); i++) { //00001 -> 11111
  47.             int sign = (__builtin_popcount(i)&1)? 1: -1;
  48.             rect area = rect(1, 1, n, n);
  49.  
  50.             for (int j = 0; j < p; j++) if (i&(1 << j)) { // 00001 00010 00100 01000 10000
  51.                 area = intersect(area, rs[j]);
  52.             }
  53.  
  54.             sum += sign*get(area)*1LL;
  55.         }
  56.  
  57.         ans = max(ans, sum);
  58.     }
  59.     cout << ans << endl;
  60. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1000000000
https://ideone.com/m3SeXY
language:
C++14 (gcc 8.3)
created:
7 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!