fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 4e2 + 5;  
  11.  
  12. int n, m, k, s;
  13. int sum[N][N], sum_s[N][N], sum_s1[N][N]; 
  14.  
  15. int a[N], dp[N]; 
  16.  
  17. void build(int sum[N][N]) {
  18.     for (int x = 1; x <= n; x++) {
  19.         for (int y = 1; y <= m; y++) {
  20.             sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1] + sum[x][y];  
  21.         }
  22.     }
  23. }
  24.  
  25. void update(int sum[N][N], int x1, int y1, int x2, int y2, int i) {
  26.     sum[x1][y1] += i;  
  27.     sum[x2 + 1][y1] -= i;  
  28.     sum[x1][y2 + 1] -= i;    
  29.     sum[x2 + 1][y2 + 1] += i;  
  30. }
  31.  
  32. ll getSum(int sum[N][N], int x1, int y1, int x2, int y2) {
  33.     return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
  34. }
  35.  
  36. int main() {
  37.     ios::sync_with_stdio(0); cin.tie(0);    
  38.     cin >> n >> m >> k >> s; 
  39.  
  40.     while (k--) {
  41.         int x, y, u, v;  
  42.         cin >> x >> y >> u >> v; 
  43.         update(sum, x, y, u, v, 1); 
  44.     }
  45.  
  46.     build(sum); 
  47.  
  48.     // sum[x][y] là số siêu thị phục vụ khu vực (x, y)
  49.     int num_happy = 0;  
  50.     for (int x = 1; x <= n; x++) {
  51.         for (int y = 1; y <= m; y++) {
  52.             num_happy += (sum[x][y] == s); 
  53.             sum_s[x][y] = (sum[x][y] == s); 
  54.             sum_s1[x][y] = (sum[x][y] == s - 1); 
  55.         }
  56.     }
  57.  
  58.     build(sum_s); 
  59.     build(sum_s1); 
  60.  
  61.     // mở thêm siêu thị mới 
  62.     int ans = 0;  
  63.     // for (int x1 = 1; x1 <= n; x1++) {
  64.     //  for (int y1 = 1; y1 <= m; y1++) {
  65.     //      for (int x2 = x1; x2 <= n; x2++) {
  66.     //          for (int y2 = y1; y2 <= m; y2++) {
  67.     //              // đếm trong hình chữ nhật (x1, y1, x2, y2) 
  68.     //              // có bao nhiêu giá trị = s và = s - 1
  69.     //              int cnt_s = getSum(sum_s, x1, y1, x2, y2); 
  70.     //              int cnt_s1 = getSum(sum_s1, x1, y1, x2, y2);            
  71.  
  72.     //              int new_num_happy = num_happy - cnt_s + cnt_s1; 
  73.     //              ans = max(ans, new_num_happy); 
  74.     //          }
  75.     //      }
  76.     //  }
  77.     // }
  78.  
  79.     for (int x1 = 1; x1 <= n; x1++) {
  80.         for (int x2 = x1; x2 <= n; x2++) {
  81.             for (int y = 1; y <= m; y++) {
  82.                 a[y] = -getSum(sum_s, x1, y, x2, y) + getSum(sum_s1, x1, y, x2, y); 
  83.             }
  84.  
  85.             int mx = -INF; 
  86.             for (int y = 1; y <= m; y++) {
  87.                 dp[y] = max(a[y], a[y] + dp[y - 1]); 
  88.                 mx = max(mx, dp[y]); 
  89.             }
  90.  
  91.             ans = max(ans, num_happy + mx); 
  92.         }
  93.     }
  94.  
  95.     cout << ans << '\n'; 
  96. }
  97.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
3 4 3 2
1 1 1 4
2 2 3 3
2 3 3 4
stdout
copy 
8
https://ideone.com/ZX0pOR
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!