Submission #986823

#	Time	Username	Problem	Language	Result	Execution time	Memory
986823		cig32	Garden (JOI23_garden)	C++17	30 / 100	3092 ms	15952 KiB

garden

#include "bits/stdc++.h"
#define int long long
using namespace std;
mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}
const int MAXN = 5e5 + 10;
int n, m, D;
int p[MAXN], q[MAXN], r[MAXN], s[MAXN];
void solve(int tc) {
  cin >> n >> m >> D;
  for(int i=0; i<n; i++) cin >> p[i] >> q[i];
  for(int i=0; i<m; i++) cin >> r[i] >> s[i];
  int ans = 1e9;
  for(int u=0; u<D; u++) {
    for(int l=0; l<D; l++) {
      int dd = u, rr = l;
      for(int i=0; i<n; i++) {
        dd = max(dd, (q[i] < u ? q[i] + D : q[i]));
        rr = max(rr, (p[i] < l ? p[i] + D : p[i]));
      }
      int x[D*2];
      for(int i=0; i<D*2; i++) x[i] = 0;
      for(int i=0; i<m; i++) {
        int xx = (r[i] < l ? r[i] + D : r[i]);
        int yy = (s[i] < u ? s[i] + D : s[i]);
        if(xx) x[xx - 1] = max(x[xx - 1], yy);
      }
      for(int i=D*2-2; i>=0; i--) {
        x[i] = max(x[i], x[i+1]);
      }
      for(int i=l; i<D*2; i++) {
        int R = max(rr, i);
        int D = max(dd, x[i]);
        ans = min(ans, (D - u + 1) * (R - l + 1));
      }
    }
  }
  cout << ans << '\n';
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
g++ T2422.cpp -std=c++17 -O2 -o T2422
./T2422 < input.txt
*/

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25