Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define all(a) (a).begin(), (a).end()
- const int maxn = 1500;
- const int maxc = 52;
- int n, C, q;
- int dp[maxn+2][maxn+2][maxc];
- void build() {
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= n; ++j)
- for (int c = 0; c < maxc; ++c)
- dp[i][j][c] += dp[i][j - 1][c] + dp[i - 1][j][c] - dp[i - 1][j - 1][c];
- }
- bool ok(int l, int r, int t, int b) {
- int res = 0;
- for (int c = 0; c < maxc; ++c) {
- int k = dp[b][r][c] - dp[b][l - 1][c] - dp[t - 1][r][c] + dp[t - 1][l - 1][c];
- res += (bool)k;
- }
- return res == C;
- }
- inline int square(int l, int r, int t, int b) {
- return (r - l + 1) * (b - t + 1);
- }
- void solve() {
- cin >> n >> C >> q;
- n += 1;
- for (int t = 0; t < q; ++t) {
- int i, j;
- char c;
- cin >> i >> j >> c;
- i += 1;
- j += 1;
- if (c >= 'a') c -= 6;
- c -= 'A';
- dp[i][j][(int)c] += 1;
- }
- build();
- int ans_l = 1;
- int ans_r = n;
- int ans_t = 1;
- int ans_b = n;
- int ans_s = 1e9;
- for (int t = 1; t <= n; ++t) {
- int b = t;
- while (b <= n && !ok(1, n, t, b)) b++;
- for (; b <= n; ++b) {
- int l = 1;
- for (int r = 1; r <= n; ++r) {
- while (l + 1 <= r && ok(l + 1, r, t, b)) {
- l++;
- }
- if (int s = square(l, r, t, b); s < ans_s && ok(l, r, t, b)) {
- ans_s = s;
- ans_l = l;
- ans_r = r;
- ans_t = t;
- ans_b = b;
- }
- }
- }
- }
- cout << ans_t - 1 << ' ' << ans_l - 1 << ' ' << ans_b - 1 << ' ' << ans_r - 1 << ' ' << ans_s << '\n';
- memset(dp, 0, sizeof dp);
- }
- signed main() {
- ios::sync_with_stdio(0); cin.tie(0);
- int t = 1;
- cin >> t;
- while (t--) {
- static int k = 0;
- cout << "Case #" << ++k << ": ";
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement