Submission #1226490

#TimeUsernameProblemLanguageResultExecution timeMemory
1226490PenguinsAreCuteCultivation (JOI17_cultivation)C++17
0 / 100
27 ms324 KiB
#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};
	for(int i=0;i<n;i++) {
		xminus.push_back(a[i]-1);
		yminus.push_back(b[i]-1);
	}
	long long ans = 4e9;
	for(auto x1: xminus)
		for(auto y1: yminus) {
			vector<int> specX = {x0+x1-1}, specY = {y0+y1-1};
			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]={1e9,1e9};
					}
					sort(pts,pts+n);
					int pmin = 1e9;
					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});
					}
				}
			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+x1+y1+cond[i-1].first+cond[i].second);
		}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...