Submission #830766

#	Time	Username	Problem	Language	Result	Execution time	Memory
830766		vjudge1	Garden (JOI23_garden)	C++17	0 / 100	3082 ms	10260 KiB

garden

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, m, d;
  cin >> n >> m >> d;
  vector<int> Xs, Ys;
  for(int i = 0, x, y; i < n; i++) {
    cin >> x >> y;
    Xs.emplace_back(x);
    Ys.emplace_back(y);
  }
  vector<pii> dbl;
  for(int i = 0, x, y; i < m; i++) {
    cin >> x >> y;
    dbl.emplace_back(x, y);
  }
  int mn = d * d;
  for(int i = 0; i < (1 << m); i++) {
    vector<int> X, Y;
    copy(all(Xs), back_inserter(X));
    copy(all(Ys), back_inserter(Y));
    for(int j =0 ; j < m; j++) {
      if(i & (1 << j)) X.emplace_back(dbl[j].first);
      else Y.emplace_back(dbl[j].second);
    }
    sort(all(X));
    sort(all(Y));
    X.erase(unique(all(X)), X.end());
    Y.erase(unique(all(Y)), Y.end());
    int mx[2] = {0, 0};
    for(int i = 0; i < sz(X); i++) {
      int prv = X[(i - 1 + sz(X)) % sz(X)];
      if(prv == X[i]) mx[0] = d;
      else mx[0] = max(mx[0], (X[i] - prv + d) % d);
    }
    for(int i = 0; i < sz(Y); i++) {
      int prv = Y[(i - 1 + sz(Y)) % sz(Y)];
      if(prv == Y[i]) mx[1] = d;
      else mx[1] = max(mx[1], (Y[i] - prv + d) % d);
    }
    //cerr << i << '\t' << mx[0] << ' ' << mx[1] << '\n';
    mx[0] = d - mx[0] + 1;
    mx[1] = d - mx[1] + 1;
    mn = min(mn, mx[0] * mx[1]);
  }
  cout << mn << '\n';
}

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

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