Submission #26396

#	Time	Username	Problem	Language	Result	Execution time	Memory
26396		pacu	Cultivation (JOI17_cultivation)	C++98	80 / 100	2000 ms	2716 KiB

cultivation

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int N;
long long rows,cols;
long long x[300],y[300];
int xid[300];
int yid[300];

bool cmpx(int a,int b)
{
	return x[a]<x[b];
}
bool cmpy(int a,int b)
{
	return y[a]<y[b];
}

int cx[600];
long long cNorth[600];
long long cSouth[600];
long long cSum[600];
int cid[600];
int C;

void getColumnVals(long long k,int loc)
{
	cx[C] = loc;
	cSum[C] = 0;
	long long pre = -1;
	for(int j=0;j<N;j++)
		if(x[yid[j]] <= loc && x[yid[j]] + k >= loc)
		{
			cSum[C] = max(cSum[C],y[yid[j]]-pre-1);
			if(pre==-1) cNorth[C] = y[yid[j]];
			pre = y[yid[j]];
		}
	cSouth[C] = rows-pre-1;
	cSum[C] = max(cSum[C],rows-pre-1);
	if(pre==-1) cSum[C] = cNorth[C] = cSouth[C] = 2000000000;
//	cout << loc << ": " << cSum[C] << ' ' << cNorth[C] << ' ' << cSouth[C] << '\n';
	C++;
}

bool cmpc(int a,int b)
{
	return cx[a]<cx[b];
}

int queSum[600];
int queNorth[600];
int queSouth[600];
int backSum,backNorth,backSouth,topSum,topNorth,topSouth;

set<int> visk;

long long getMinSum(int k)
{
	if(visk.find(k) != visk.end()) return 2000000000;
	visk.insert(k);
	C = 0;
	for(int i=0;i<N;i++)
		getColumnVals(k,x[xid[i]]);
	for(int i=0;i<N;i++)
		getColumnVals(k,x[xid[i]]+k+1);
	for(int i=0;i<C;i++)
		cid[i] = i;
	sort(cid,cid+C,cmpc);
	backSum = backNorth = backSouth = 0;
	topSum = topNorth = topSouth = 0;
	long long ans = 2000000000;
	for(int i=C-1;i>=0;i--)
	{
		int cur = cid[i];
		while(backSum < topSum && cx[queSum[backSum]]-cx[cur] >= cols)
			backSum++;
		while(backNorth < topNorth && cx[queNorth[backNorth]]-cx[cur] >= cols)
			backNorth++;
		while(backSouth < topSouth && cx[queSouth[backSouth]]-cx[cur] >= cols)
			backSouth++;
		while(backSum < topSum && cSum[cur] >= cSum[queSum[topSum-1]])
			topSum--;
		while(backNorth < topNorth && cNorth[cur] >= cNorth[queNorth[topNorth-1]])
			topNorth--;
		while(backSouth < topSouth && cSouth[cur] >= cSouth[queSouth[topSouth-1]])
			topSouth--;
		queSum[topSum++] = cur;
		queNorth[topNorth++] = cur;
		queSouth[topSouth++] = cur;
		ans = min(ans,max(cSum[queSum[backSum]],cNorth[queNorth[backNorth]]+cSouth[queSouth[backSouth]]));
	}
	return ans+k;
}

int main()
{
	cin >> cols >> rows;
	cin >> N;
	for(int i=0;i<N;i++)
	{
		cin >> x[i] >> y[i];
		y[i]--,x[i]--;
		xid[i] = yid[i] = i;
	}
	sort(xid,xid+N,cmpx);
	sort(yid,yid+N,cmpy);
	long long ans = 2000000000;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		{
			if(x[xid[j]]>x[xid[i]])
				ans = min(ans,getMinSum(x[xid[j]]-x[xid[i]]-1));
			ans = min(ans,getMinSum(x[xid[i]]+cols-1-x[xid[j]]));
		}
	cout << ans << '\n';
}

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