Hướng dẫn giải của duong3982oj Contest 01 - Bảng đẹp
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Subtask 1
Duyệt mọi bảng con, và sử dụng mảng cộng dồn để kiểm tra bảng con đẹp lớn nhất.
Độ phức tạp: ~O~ ~(n^3)~.
Subtask 2
Thay vì duyệt độ dài, ta sẽ tìm kiếm nhị phân độ dài đó.
Để tối ưu hơn, ta có thể đặt ~l = res + 1~ và ~r = n~, với ~l, r~ là hai biên tìm kiếm, và ~res~ là kết quả hiện tại.
Độ phức tạp: ~O~ ~(n^2 \times log (n))~, nhưng thực tế sẽ nhanh hơn nhiều.
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e3 + 9;
int n, m, k, a[N][N], s[N][N];
bool check (int i, int j, int val){
if (val == 0) return 1;
return s[i + val - 1][j + val - 1] - s[i - 1][j + val - 1] - s[i + val - 1][j - 1] + s[i - 1][j - 1] <= k;
}
signed main (){
ios_base::sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
int res = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (check (i, j, res) == 0) continue;
int l = res, r = min (n - i + 1, m - j + 1);
while (l <= r){
int mid = l + r >> 1;
if (check (i, j, mid)){
res = mid; l = mid + 1;
} else r = mid - 1;
}
}
}
cout << res;
}
Bình luận