제출 #1225242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225242		emptypringlescan	Cultivation (JOI17_cultivation)	C++17	0 / 100	1 ms	324 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
long long row,col;
int n;
pair<long long,long long> arr[305];
pair<long long,long long> mx,my;
vector<long long> impty;
multiset<long long> st,en,l,r,both;
int ded=0;
void nxtst(long long x, bool rep){
	//cout << "Add st: " << x << '\n';
	if(x>0){
		auto it=st.lower_bound(x);
		long long b=*it;
		it--;
		long long a=*it;
		if(b-a>1){
			if(a==0&&b==row+1) ded--;
			else if(a==0) l.erase(l.find(b-a-1));
			else if(b==row+1) r.erase(r.find(b-a-1));
			else both.erase(both.find(b-a-1));
		}
		st.insert(x);
		if(rep){
			if(x-a>1){
				if(a==0) l.insert(x-a-1);
				else both.insert(x-a-1);
			}
			if(b-x>1){
				if(b==row+1) r.insert(b-x-1);
				else both.insert(b-x-1);
			}
		}
	}
	else{
		x=-x;
		st.erase(st.find(x));
		auto it=st.lower_bound(x);
		long long b=*it;
		it--;
		long long a=*it;
		if(x-a>1){
			if(a==0) l.erase(l.find(x-a-1));
			else both.erase(both.find(x-a-1));
		}
		if(b-x>1){
			if(b==row+1) r.erase(r.find(b-x-1));
			else both.erase(both.find(b-x-1));
		}
		if(rep){
			if(b-a>1){
				if(a==0&&b==row+1) ded++;
				else if(a==0) l.insert(b-a-1);
				else if(b==row+1) r.insert(b-a-1);
				else both.insert(b-a-1);
			}
		}
	}
	//cout << ded << '\n';
}
void nxten(long long x, bool rep){
	//cout << "Add en: " << x << '\n';
	if(x>0){
		auto it=en.lower_bound(x);
		long long b=*it;
		it--;
		long long a=*it;
		if(rep){
			if(b-a>1){
				if(a==0&&b==row+1) ded--;
				else if(a==0) l.erase(l.find(b-a-1));
				else if(b==row+1) r.erase(r.find(b-a-1));
				else both.erase(both.find(b-a-1));
			}
		}
		en.insert(x);
		if(x-a>1){
			if(a==0) l.insert(x-a-1);
			else both.insert(x-a-1);
		}
		if(b-x>1){
			if(b==row+1) r.insert(b-x-1);
			else both.insert(b-x-1);
		}
	}
	else{
		x=-x;
		en.erase(en.find(x));
		auto it=en.lower_bound(x);
		long long b=*it;
		it--;
		long long a=*it;
		if(rep){
			if(x-a>1){
				if(a==0) l.erase(l.find(x-a-1));
				else both.erase(both.find(x-a-1));
			}
			if(b-x>1){
				if(b==row+1) r.erase(r.find(b-x-1));
				else both.erase(both.find(b-x-1));
			}
		}
		if(b-a>1){
			if(a==0&&b==row+1) ded++;
			else if(a==0) l.insert(b-a-1);
			else if(b==row+1) r.insert(b-a-1);
			else both.insert(b-a-1);
		}
	}
//	cout << ded << '\n';
}
long long getans(){
	if(ded) return 1e16;
	long long x=0,y=0,z=0;
	if(!l.empty()) x=*(--l.end());
	if(!r.empty()) y=*(--r.end());
	if(!both.empty()) z=*(--both.end());
	//cout << x << ' ' << y << ' ' << z << '\n';
	if(x+y>z) return x+y;
	else return z;
}
bool cmp(pair<long long,long long> a,pair<long long,long long> b){
	if(a.first!=b.first) return a.first<b.first;
	else return a.second>b.second;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> row >> col;
	cin >> n;
	mx={1e16,-1}; my={1e16,-1};
	for(int i=0; i<n; i++){
		cin >> arr[i].first >> arr[i].second;
		mx.first=min(mx.first,arr[i].first);
		mx.second=max(mx.second,arr[i].first);
		my.first=min(my.first,arr[i].second);
		my.second=max(my.second,arr[i].second);
	}
	impty.push_back(my.first-1+col-my.second);
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(abs(arr[i].second-arr[j].second)>my.first-1+col-my.second){
				impty.push_back(abs(arr[i].second-arr[j].second)-1);
			}
		}
	}
	sort(impty.begin(),impty.end());
	long long ans=1e16;
	for(long long i:impty){
		vector<pair<long long,long long> > imptx;
		for(int j=0; j<n; j++){
			imptx.push_back({arr[j].second,arr[j].first});
			imptx.push_back({arr[j].second+i+1,-arr[j].first});
		}
		sort(imptx.begin(),imptx.end(),cmp);
		st.clear(); en.clear(); l.clear(); r.clear(); both.clear();
		ded=my.first-1;
		st.insert(0); st.insert(row+1);
		en.insert(0); en.insert(row+1);
		//cout << i << '\n';
		int cnt=0;
		pair<long long,long long> prev={-999,-1e16};
		for(auto j:imptx){
			if(j.first<=row){
				nxten(j.second,prev.first==j.first);
				cnt++;
				prev=j;
			}
			else break;
		}
		//cout << "Check: " << getans() << ' ' << getans()+i << '\n';
		ans=min(ans,getans()+i);
		for(int j=0; j<(int)imptx.size(); j++){
			if(imptx[j].first>my.first) break;
			nxtst(imptx[j].second,(j==0||imptx[j].first==imptx[j-1].first));
			while(cnt<(int)imptx.size()&&imptx[cnt].first<=imptx[j].first+row){
				nxten(imptx[cnt].second,(cnt==0||imptx[cnt].first==imptx[cnt-1].first));
				cnt++;
			}
			if(j==(int)imptx.size()-1||imptx[j].first!=imptx[j+1].first){
				ans=min(ans,getans()+i);
				//cout << "Check: " << getans() << ' ' << getans()+i << '\n';
			}
		}
	}
	cout << ans;
}

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