Submission #909970

#	Time	Username	Problem	Language	Result	Execution time	Memory
909970		Nonoze	Garden (JOI23_garden)	C++17	45 / 100	3018 ms	13012 KiB

garden

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) (int)(x.size())


int n, m, D;
vector<int> p, q;
vector<int> r, s;

int subtask4() {
	int ans=D*D;
	for (int a=0; a<D; a++) {
		for (int b=0; b<D; b++) {
			for (int c=a; c<=a+D; c++) {
				for (int d=b; d<=b+D; d++) {
					if ((c-a+1)*(d-b+1)>=ans) continue;
					bool flag=true;
					for (int i=0; i<n; i++) {
						if ((p[i]>=a && p[i]<=c) || (c>=D && p[i]<=c%D)) {
							if ((q[i]>=b && q[i]<=d) || (d>=D && q[i]<=d%D)) {
								continue;
							}
						}
						flag=false;
						break;
					}
					if (!flag) {
						continue;
					}
					for (int i=0; i<m; i++) {
						if ((r[i]>=a && r[i]<=c) || (c>=D && r[i]<=c%D)) {
							continue;
						}
						if ((s[i]>=b && s[i]<=d) || (d>=D && s[i]<=d%D)) {
							continue;
						}
						flag=false;
						break;
					}
					if (flag) {
						ans=min(ans, (c-a+1)*(d-b+1));
					}
				}
			}
		}
	}
	return ans;
}

vector<bool> x(5000, false), y(5000, false);

int bruteforces(int empl) {
	if (empl==m) {
		int xmax=0, prec=0, prem=-1;
		for (int i=0; i<D; i++) {
			xmax=max(xmax, i-prec-1);
			if (x[i]) {
				prec=i;
				if (prem==-1) prem=i;
			}
		}
		xmax=D-xmax;
		xmax=min(xmax, prec-prem+1);
		int ymax=0;
		prec=0, prem=-1;
		for (int i=0; i<D; i++) {
			ymax=max(ymax, i-prec-1);
			if (y[i]) {
				prec=i;
				if (prem==-1) prem=i;
			}
		}
		ymax=D-ymax;
		ymax=min(ymax, prec-prem+1);
		return xmax*ymax;
	}
	bool xx=x[r[empl]], yy=y[s[empl]];
	x[r[empl]]=true;
	int ans=bruteforces(empl+1);
	x[r[empl]]=xx;
	y[s[empl]]=true;
	ans=min(ans, bruteforces(empl+1));
	y[s[empl]]=yy;
	return ans;
}

int subtask1() {
	for (auto u: p) x[u]=true;
	for (auto u: q) y[u]=true;
	return bruteforces(0);
}

int solve() {
	cin >> n >> m >> D;
	p.resize(n);
	q.resize(n);
	r.resize(m);
	s.resize(m);
	for (int i=0; i<n; i++) {
		cin >> p[i] >> q[i];
	}
	for (int i=0; i<m; i++) {
		cin >> r[i] >> s[i];
	}
	if (D<=100 && n+m<=5000) return subtask4();
	return subtask1();
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << solve() << endl;
	return 0;
}

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