Advertisement
Gosunov

Reply Challenge Miner#4

Mar 28th, 2023
1,240
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(a) (a).begin(), (a).end()
  4.  
  5. const int maxn = 1500;
  6. const int maxc = 52;
  7.  
  8. int n, C, q;
  9.  
  10. int dp[maxn+2][maxn+2][maxc];
  11.  
  12. void build() {
  13.     for (int i = 1; i <= n; ++i)
  14.         for (int j = 1; j <= n; ++j)
  15.             for (int c = 0; c < maxc; ++c)
  16.                 dp[i][j][c] += dp[i][j - 1][c] + dp[i - 1][j][c] - dp[i - 1][j - 1][c];
  17. }
  18.  
  19. bool ok(int l, int r, int t, int b) {
  20.     int res = 0;
  21.     for (int c = 0; c < maxc; ++c) {
  22.         int k = dp[b][r][c] - dp[b][l - 1][c] - dp[t - 1][r][c] + dp[t - 1][l - 1][c];
  23.         res += (bool)k;
  24.     }
  25.     return res == C;
  26. }
  27.  
  28. void solve() {
  29.     cin >> n >> C >> q;
  30.     n += 1;
  31.  
  32.     for (int t = 0; t < q; ++t) {
  33.         int i, j;
  34.         char c;
  35.         cin >> i >> j >> c;
  36.         i += 1;
  37.         j += 1;
  38.         if (c >= 'a') c -= 6;
  39.         c -= 'A';
  40.         dp[i][j][(int)c] += 1;
  41.     }
  42.     build();
  43.    
  44.     int ans_l = 1;
  45.     int ans_r = n;
  46.     int ans_t = 1;
  47.     int ans_b = n;
  48.     int ans_s = 1e9;
  49.     for (int t = 1; t <= n; ++t) {
  50.         int b = t;
  51.         while (b <= n && !ok(1, n, t, b)) b++;
  52.         int s = b - t + 1;
  53.         for (; b <= n; ++b) {
  54.             int l = 1;
  55.             for (int r = 1; r <= n; ++r) {
  56.                 s += b - t + 1;
  57.                 if (s >= ans_s) continue;
  58.  
  59.                 while (l + 1 <= r && ok(l + 1, r, t, b)) {
  60.                     l++;
  61.                     s -= b - t + 1;
  62.                 }
  63.                 if (s < ans_s && ok(l, r, t, b)) {
  64.                     ans_s = s;
  65.                     ans_l = l;
  66.                     ans_r = r;
  67.                     ans_t = t;
  68.                     ans_b = b;
  69.                 }
  70.             }
  71.         }
  72.     }
  73.     cout << ans_t - 1 << ' ' << ans_l - 1 << ' ' << ans_b - 1 << ' ' << ans_r - 1 << ' ' << ans_s << '\n';
  74.     memset(dp, 0, sizeof dp);
  75. }
  76.  
  77. signed main() {
  78.     ios::sync_with_stdio(0); cin.tie(0);
  79.     int t = 1;
  80.     cin >> t;
  81.     while (t--) {
  82.         static int k = 0;
  83.         cout << "Case #" << ++k << ": ";
  84.         solve();
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement