fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. // Giả sử ta mở thêm 1 siêu thị phục vụ các khu vực dân cư nằm trong hình chữ nhật (x1, y1, x2, y2)
  12. // Khi đó số khu vực dân cư có đúng s siêu thị phục vụ hiện tại
  13. // = Số khu vực dân cư có đúng s siêu thị phục vụ ban đầu 
  14. //   - (Số khu vực dân cư trong hcn(x1, y1, x2, y2) có đúng s siêu thị phục vụ)
  15. //   + (Số khu vực dân cư trong hcn(x1, y1, x2, y2) có đúng s-1 siêu thị phục vụ)
  16. // => Bài toán tìm hình chữ nhật có tổng lớn nhất
  17. const int N = 4e2 + 5;  
  18.  
  19. int n, m, k, s;
  20. int cnt[N][N]; 
  21. int sum[N][N];
  22.  
  23. ll getSum(int x1, int y1, int x2, int y2) {
  24.     return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
  25. }
  26.  
  27. int a[N]; 
  28. int dp[N]; // dp[i] = Đoạn con có tổng lớn nhất kết thúc tại i 
  29.  
  30. int main() {
  31.     ios::sync_with_stdio(false); 
  32.     cin.tie(nullptr);    
  33.     cin >> n >> m >> k >> s; 
  34.  
  35.     for (int i = 0; i < k; i++) {
  36.         // Siêu thị thứ i phục vụ các khu vực dân cư nằm trong hình chữ nhật (x1, y1, x2, y2)
  37.         int x1, y1, x2, y2;  
  38.         cin >> x1 >> y1 >> x2 >> y2;  
  39.         // Update hình chữ nhật (x1, y1, x2, y2) lên thêm 1 đơn vị
  40.         cnt[x1][y1]++;  
  41.         cnt[x2 + 1][y1]--;  
  42.         cnt[x1][y2 + 1]--;    
  43.         cnt[x2 + 1][y2 + 1]++;
  44.     }
  45.  
  46.     for (int x = 1; x <= n; x++) {
  47.         for (int y = 1; y <= m; y++) {
  48.             cnt[x][y] = cnt[x - 1][y] + cnt[x][y - 1] - cnt[x - 1][y - 1] + cnt[x][y];  
  49.         }
  50.     }
  51.     // Lúc này cnt[x][y] = Số siêu thị phục vụ khu vực dân cư (x, y)
  52.  
  53.     int num_happy = 0; // Số khu vực dân cư có đúng s siêu thị phục vụ ban đầu 
  54.     for (int x = 1; x <= n; x++) {
  55.         for (int y = 1; y <= m; y++) {
  56.             num_happy += (cnt[x][y] == s); 
  57.             sum[x][y] = (cnt[x][y] == s - 1) - (cnt[x][y] == s); 
  58.         }
  59.     }
  60.  
  61.     for (int x = 1; x <= n; x++) {
  62.         for (int y = 1; y <= m; y++) {
  63.             sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1] + sum[x][y]; 
  64.         }
  65.     }
  66.  
  67.     // Mở thêm siêu thị mới 
  68.     // int ans = 0;  
  69.     // for (int x1 = 1; x1 <= n; x1++) {
  70.     //     for (int y1 = 1; y1 <= m; y1++) {
  71.     //         for (int x2 = x1; x2 <= n; x2++) {
  72.     //             for (int y2 = y1; y2 <= m; y2++) {
  73.     //                 int new_num_happy = num_happy + getSum(x1, y1, x2, y2); 
  74.     //                 ans = max(ans, new_num_happy); 
  75.     //             }
  76.     //         }
  77.     //     }
  78.     // } // O(n^2 * m^2)
  79.  
  80.     // Ý tưởng tối ưu: Ta sẽ duyệt qua và cố định x1, x2
  81.     // Lúc này ta sẽ chỉ xét các hình chữ nhật (x1', y1', x2', y2') có x1' = x1 và x2' = x2
  82.     // Nhận xét: Tổng của 1 hình chữ nhật lúc này có thể biểu diễn bằng tổng của các cột nằm liên tiếp nhau
  83.     // => Đặt a[y] = Tổng của cột thứ y (1 <= y <= m)
  84.     // => Đưa về Bài toán tìm đoạn con có tổng lớn nhất của mảng a 
  85.     // => Bài toán kinh điển có thể giải quyết bằng dp  
  86.     int ans = 0; 
  87.     for (int x1 = 1; x1 <= n; x1++) {
  88.         for (int x2 = x1; x2 <= n; x2++) {
  89.             for (int y = 1; y <= m; y++) {
  90.                 a[y] = getSum(x1, y, x2, y); 
  91.             }
  92.  
  93.             int mx = -INF; 
  94.             for (int i = 1; i <= m; i++) {
  95.                 dp[i] = max(a[i], dp[i - 1] + a[i]); 
  96.                 mx = max(mx, dp[i]); 
  97.             }
  98.  
  99.             ans = max(ans, num_happy + mx); 
  100.         }
  101.     } // O(n^2 * m)
  102.  
  103.     cout << ans << '\n'; 
  104. }
  105.  
Success #stdin #stdout 0.01s 5280KB
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/MuOLRd
language:
C++14 (gcc 8.3)
created:
19 days 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!