Submission #59811

#	Time	Username	Problem	Language	Result	Execution time	Memory
59811		khsoo01	Cultivation (JOI17_cultivation)	C++11	5 / 100	26 ms	648 KiB

cultivation

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll N = 305, inf = 1e18;

ll r, c, n, x[N], y[N], ans = inf;

vector<ll> pnt[N], slc[2*N];

struct compressor {
	vector<ll> v;
	ll sz () {
		return (int)v.size();
	}
	void ins (ll X) {
		v.push_back(X);
	}
	ll get (ll X) {
		return lower_bound(v.begin(), v.end(), X) - v.begin();
	}
	void calc () {
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}
} xcp;

struct segment {
	ll s, e, x;
	segment (ll S, ll E, ll X) {
		s = S;
		e = E;
		x = X;
	}
	segment () {
		segment(0, 0, 0);
	}
	bool valid () {
		return (!!s && s < e);
	}
	bool operator == (const segment &T) const {
		return (s == T.s && e == T.e && x == T.x);
	}
	bool operator < (const segment &T) const {
		return (x == T.x ? s < T.s : x < T.x);
	}
};

void update (vector<segment> &V, ll X, segment S) {
	if(!S.valid()) return;
	S.e -= c - 1;
	if(!S.valid()) return;
	S.e = min(S.e, X + 2);
	if(!S.valid()) return;
	V.push_back(S);
}

vector<segment> gen_vector (ll X) {
	vector<segment> R;
	for(ll i=0;i<xcp.sz();i++) {
		segment C = segment(0, 0, xcp.v[i]);
		for(auto &T : pnt[i]) {
			if(C.e >= T) {
				if(!C.valid()) C.s = T;
				C.e = T+X+1;
			}
			else {
				update(R, X, C);
				C = segment(T, T+X+1, xcp.v[i]);
			}
		}
		update(R, X, C);
	}
	compressor Y;
	for(auto &T : R) {
		Y.ins(T.s);
		Y.ins(T.e);
	}
	Y.calc();
	for(auto &T : R) {
		T.s = Y.get(T.s);
		T.e = Y.get(T.e);
	}
	return R;
}

ll solve (vector<segment> &V) {
	ll ymx = 0, R = inf;
	for(int i=0;i<2*n;i++) {
		slc[i].clear();
	}
	for(auto &T : V) {
		ymx = max(ymx, T.e);
		for(int i=T.s;i<T.e;i++) {
			slc[i].push_back(T.x);
		}
	}
	for(int i=0;i<ymx;i++) {
		if(slc[i].empty()) continue;
		slc[i].push_back(slc[i][0] + r);
		ll C = 0;
		for(int j=1;j<(int)slc[i].size();j++) {
			C = max(C, slc[i][j] - slc[i][j-1] - 1);
		}
		R = min(R, C);
	}
	return R;
}

int main()
{
	scanf("%lld%lld%lld",&r,&c,&n);
	ll ymn = inf;
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&x[i],&y[i]);
		xcp.ins(x[i]);
		ymn = min(ymn, y[i]);
	}
	xcp.calc();
	for(ll i=1;i<=n;i++) {
		y[i] -= ymn - 1;
		pnt[xcp.get(x[i])].push_back(y[i]);
	}
	for(ll i=0;i<xcp.sz();i++) {
		sort(pnt[i].begin(), pnt[i].end());
	}
	auto prv = gen_vector(0);
	ans = min(ans, solve(prv));
	for(ll I = 0;;) {
		ll S = 1, E = 2*c-I;
		while(S<E) {
			ll M = (S+E)/2;
			gen_vector(I+M) == prv ? S = M+1 : E = M;
		}
		auto V = gen_vector(I+S);
		if(V == prv) break;
		I += S;
		ans = min(ans, solve(V) + I);
		swap(prv, V);
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&r,&c,&n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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