Submission #1226512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226512		PenguinsAreCute	Cultivation (JOI17_cultivation)	C++17	5 / 100	2096 ms	16928 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, x0, y0;
	cin >> x0 >> y0 >> n;
	int a[n], b[n];
	for(int i=0;i<n;i++)
		cin >> a[i] >> b[i];
	vector<int> xminus = {0}, yminus = {0}, xplus = {0}, yplus = {0};
	for(int i=0;i<n;i++) {
		xminus.push_back(a[i]-1);
		xplus.push_back(x0-a[i]);
		yminus.push_back(b[i]-1);
		yplus.push_back(y0-a[i]);
	}
	long long ans = 4e9;
	for(auto west: xminus)
		for(auto east: xplus) {
			vector<int> spec = {1};
			for(int i=0;i<n;i++) {
				spec.push_back(max(1,a[i]-west));
				spec.push_back(min(x0,a[i]+east)+1);
			}
			sort(spec.begin(),spec.end());
			spec.resize(unique(spec.begin(),spec.end())-spec.begin());
			if(spec.back() == x0 + 1)
				spec.pop_back();
			int impt = spec.size();
			vector<int> pts[impt];
			for(int i=0;i<n;i++) {
				for(int j=0;j<impt;j++)
					if(a[i]-west <= spec[j] && spec[j] <= a[i]+east)
						pts[j].push_back(b[i]);
			}
			int minTot = 0, minNorth = 0, minSouth = 0;
			for(int i=0;i<impt;i++) {
				sort(pts[i].begin(),pts[i].end());
				int sz = pts[i].size();
				if(sz == 0) {
					minTot = 2e9;
					break;
				}
				for(int j=0;j<sz-1;j++)
					minTot = max(minTot,pts[i][j+1]-pts[i][j]-1);
				minNorth = max(minNorth,y0-pts[i][sz-1]);
				minSouth=max(minSouth,pts[i][0]-1);
			}
			ans = min(ans, 0LL + max(minTot,minNorth+minSouth) + west + east);
		}
	for(auto south: yminus)
		for(auto north: yplus) {
			vector<int> spec = {1};
			for(int i=0;i<n;i++) {
				spec.push_back(max(1,b[i]-south));
				spec.push_back(min(y0,b[i]+north)+1);
			}
			sort(spec.begin(),spec.end());
			spec.resize(unique(spec.begin(),spec.end())-spec.begin());
			if(spec.back() == y0 + 1)
				spec.pop_back();
			int impt = spec.size();
			vector<int> pts[impt];
			for(int i=0;i<n;i++) {
				for(int j=0;j<impt;j++)
					if(b[i]-south <= spec[j] && spec[j] <= b[i]+north)
						pts[j].push_back(b[i]);
			}
			int minTot = 0, minEast = 0, minWest = 0;
			for(int i=0;i<impt;i++) {
				sort(pts[i].begin(),pts[i].end());
				int sz = pts[i].size();
				if(sz == 0) {
					minTot = 2e9;
					break;
				}
				for(int j=0;j<sz-1;j++)
					minTot = max(minTot,pts[i][j+1]-pts[i][j]-1);
				minEast = max(minEast,x0-pts[i][sz-1]);
				minWest=max(minWest,pts[i][0]-1);
			}
			ans = min(ans, 0LL + max(minTot,minEast+minWest) + south + north);
		}
	if(int x1=0;1)
		if(int y1=0;1) {
			vector<int> specX = {x0+x1}, specY = {y0+y1};
			for(int i=0;i<n;i++) {
				if(a[i]-x1-1 >= 1)
					specX.push_back(a[i]-1);
				if(b[i]-y1-1 >= 1)
					specY.push_back(b[i]-1);
			}
			vector<pair<int,int>> cond;
			for(auto xs: specX)
				for(auto ys: specY) {
					pair<int,int> pts[n];
					for(int i=0;i<n;i++) {
						if(a[i] <= xs && b[i] <= ys)
							pts[i] = {xs-a[i],ys-b[i]};
						else
							pts[i]={2e9,2e9};
					}
					sort(pts,pts+n);
					int pmin = 2e9;
					cond.push_back({pts[0].first,2e9});
					for(int i=0;i<n;i++) {
						pmin = min(pmin, pts[i].second);
						cond.push_back({(i==n-1?2e9:pts[i+1].first),pmin});
					}
				}
			cond.push_back({2e9,y1});
			cond.push_back({x1,2e9});
			sort(cond.begin(),cond.end());
			int sz = cond.size();
			for(int i=sz-1;i--;)
				cond[i].second = max(cond[i].second, cond[i+1].second);
			for(int i=1;i<sz;i++)
				ans = min(ans, 0LL+cond[i-1].first+cond[i].second);
		}
	cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20