Submission #1075511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075511		qwerasdfzxcl	Cultivation (JOI17_cultivation)	C++17	100 / 100	1727 ms	4752 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 4e18;

pair<ll, ll> P[303];
ll a[303], S[707], E[707], X[3][707], dp[303][303], FUCK[2][303][303], L, U;
int dq[3][707], n;

pair<ll, int> V[303];
int f[303], g[303];

ll solve(ll len){
	int sz = 0;

	for (int i=1,j=1;i<=n||j<=n;){
		ll s = min(a[i], a[j]+len);
		while(a[i]==s || a[j]+len==s){
			if (a[i]==s) i++;
			if (a[j]+len==s) j++;
		}

		if (j > n) break;
		ll e = min(a[i], a[j]+len);

		assert(j < i);
	
		++sz;
		S[sz] = s, E[sz] = e;
		X[0][sz] = FUCK[0][j][i-1], X[1][sz] = FUCK[1][j][i-1], X[2][sz] = dp[j][i-1];

	}

	ll ret = INF;
	int pl[3] = {1, 1, 1}, pr[3] = {1, 1, 1};

	for (int i=1,j=1;i<=sz;i++){
		for (int z=0;z<3;z++) while(pl[z] < pr[z] && dq[z][pl[z]] < i) pl[z]++;
		while(j <= sz && E[j-1]-S[i] < L){
			for (int z=0;z<3;z++){
				while(pl[z] < pr[z] && X[z][dq[z][pr[z]-1]] <= X[z][j]) pr[z]--;
				dq[z][pr[z]] = j;
				pr[z]++;
			}
			j++;
		}

		if (j > sz && E[j-1]-S[i] < L) break;
		for (int z=0;z<3;z++) assert(pl[z] < pr[z]);

		ret = min(ret, max(X[0][dq[0][pl[0]]] + X[1][dq[1][pl[1]]], X[2][dq[2][pl[2]]]));
	}

	return ret + len - 1;
}

int main(){
	scanf("%lld %lld", &L, &U);
	scanf("%d", &n);
	for (int i=1;i<=n;i++) scanf("%lld %lld", &P[i].first, &P[i].second);
	sort(P+1, P+n+1);

	auto st = clock();

	for (int i=1;i<=n;i++) a[i] = P[i].first;
	for (int i=n;i>0;i--){
		int sz = 0;
		V[sz++] = {0, 0};
		for (int j=n;j>=i;j--){
			V[sz++] = {P[j].second, j};
		}
		V[sz++] = {U+1, n+1};
		sort(V, V+sz);

		for (int i=0;i<sz-1;i++) f[V[i].second] = V[i+1].second, g[V[i+1].second] = V[i].second;

		for (int j=1;j<sz;j++) dp[i][n] = max(dp[i][n], V[j].first - V[j-1].first - 1);
		FUCK[0][i][n] = P[f[0]].second - 1;
		FUCK[1][i][n] = U - P[g[n+1]].second;

		for (int j=n-1;j>=i;j--){
			int ff = f[j+1], gg = g[j+1];
			g[ff] = gg;
			f[gg] = ff;

			dp[i][j] = max(dp[i][j+1], P[ff].second - P[gg].second - 1);
			FUCK[0][i][j] = P[f[0]].second - 1;
			FUCK[1][i][j] = U - P[g[n+1]].second;
		}
	}

	ll mn = 0;
	for (int i=2;i<=n;i++) mn = max(mn, a[i] - a[i-1]);
	mn = max(mn, (L-a[n]) + a[1]);
	a[n+1] = INF;

	ll ans = INF;
	vector<ll> C = {L};
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			if (a[j]-a[i] >= mn) C.push_back(a[j]-a[i]);
			if (L-a[j]+a[i] >= mn) C.push_back(L-a[j]+a[i]);
			if (L+a[j]-a[i] >= mn) C.push_back(L+a[j]-a[i]);
		}
	}

	sort(C.begin(), C.end());
	C.erase(unique(C.begin(), C.end()), C.end());

	assert((double)(clock() - st) / CLOCKS_PER_SEC < 0.7);
	for (auto &x:C) ans = min(ans, solve(x));

	cout << ans << '\n';
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%lld %lld", &L, &U);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
cultivation.cpp:62:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  for (int i=1;i<=n;i++) scanf("%lld %lld", &P[i].first, &P[i].second);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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