fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. // #define int long long
  5. #define ft first
  6. #define sc second
  7. using pii = pair<int, int>;
  8. const int N = 355;
  9. const int K = N * N + 5;
  10.  
  11. int n, m, k;
  12. pii a[K];
  13. int f[N][N];
  14. int ans[K];
  15.  
  16. signed main() {
  17.     cin.tie(NULL)->sync_with_stdio(false);
  18.     if(ifstream("PHITIEU.inp")) {
  19.         freopen("PHITIEU.inp", "r", stdin);
  20.         freopen("PHITIEU.out", "w", stdout);
  21.     }
  22.     cin >> n >> m >> k;
  23.     for (int i = 1; i <= k; i++) cin >> a[i].ft >> a[i].sc;
  24.  
  25.     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) f[i][j] = k + 1;
  26.     for (int i = 1; i <= k; i++) {
  27.         int x = a[i].ft, y = a[i].sc;
  28.         f[x][y] = min(f[x][y], i);
  29.     }
  30.  
  31.     for (int len = 1; len <= min(n, m); len++) {
  32.         if (len != 1) {
  33.             for (int i = 1; i + len - 1 <= n; i++) {
  34.                 for (int j = 1; j + len - 1 <= m; j++) {
  35.                     f[i][j] = min({f[i][j], f[i + 1][j], f[i][j + 1], f[i + 1][j + 1]});
  36.                 }
  37.             }
  38.         }
  39.  
  40.         int mx = 1;
  41.         for (int i = 1; i + len - 1 <= n; i++) {
  42.             for (int j = 1; j + len - 1 <= m; j++) {
  43.                 mx = max(mx, f[i][j]);
  44.             }
  45.         }
  46.         ans[mx - 1] = max(ans[mx - 1], len);
  47.     }
  48.  
  49.     for (int i = k; i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
  50.     for (int i = 1; i <= k; i++) cout << ans[i] << "\n";
  51.     return 0;
  52. }
  53.  
  54. /*
  55. Gọi d[i][j] là thời gian quả bóng ở ô i j nổ
  56. vậy thời gian mà hình vuông đó không còn chính là min của các ô vuông con
  57. (hay thời gian để hình vuông đang xét bắt đầu tại i, j, độ dài là len không còn là:
  58. min {d[i][j] -> d[i + len - 1][j + len - 1]} )
  59.  
  60. Nếu cố định độ dài đang xét là len, nếu max thời gian của các hình vuông bằng T
  61. thì có nghĩa là khoảng khắc từ 1 -> (T - 1) sẽ tồn tại hình vuông có độ dài = len thỏa mãn 
  62.  
  63. Vậy với mỗi len thì 1 <= i <= T - 1: ans[i] = max(ans[i], len) 
  64. ta có thể dễ dàng xử lý bằng suffix max (dòng 46 và 49)
  65.  
  66. vậy làm sao để tính nhanh các min các ô vuông từ d[i][j] -> d[i + len - 1][j + len - 1] ?
  67. gọi f[len][i][j] là min của các ô vuông từ d[i][j] -> d[i + len - 1][j + len - 1]
  68. khi đó với 2 <= len <= min(n, m) dễ dàng tính được: f[len][i][j] = min({f[len - 1][i][j],
  69.                                                                         f[len - 1][i + 1][j],
  70.                                                                         f[len - 1][i][j + 1],
  71.                                                                         f[len - 1][i + 1][j + 1]})
  72. (Dòng 35)
  73.  
  74. (P/S ta không cần lưu chiều len, bằng cách duyệt len từ 1 -> n và chỉ sài mảng f[i][j], ta sẽ tối ưu được bộ nhớ xuống còn n * m)
  75.  
  76.  
  77. Vậy độ phức tạp bài này là: O(min(n, m) * n * m) ≈ n ^ 3
  78. */
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Ykr6BU
author: NeOWami
language:
C++14 (gcc 8.3)
created:
1 day 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!