Submission #1075356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075356		qwerasdfzxcl	Cultivation (JOI17_cultivation)	C++17	0 / 100	2045 ms	348 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[303], E[303], X[303], dp[303][303], L, U;
int dq[303], n;

ll solve(ll len){
	// printf(" solve %lld\n", 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);

		if (sz > 0 && X[sz] == dp[j][i-1]) E[sz] = e;
		else{
			++sz;
			S[sz] = s, E[sz] = e, X[sz] = dp[j][i-1];
			// printf(" fuck %d %d -> %lld\n", j, i-1, X[sz]);
		}
	}

	// for (int i=1;i<=sz;i++) printf(" (%lld, %lld, %lld)", S[i], E[i], X[i]);
	// printf("\n");

	ll ret = INF;

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

		if (j > sz+1) break;
		assert(pl < pr);

		ret = min(ret, X[dq[pl]]);
	}

	return ret + len - 2;
}

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);

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

		sort(V.begin(), V.end());
		for (int j=1;j<(int)V.size();j++) dp[i][n] = max(dp[i][n], V[j] - V[j-1]);
		// printf(" ok %d %d -> %lld\n", i, n, dp[i][n]);

		for (int j=n-1;j>=i;j--){
			int idx = find(V.begin(), V.end(), P[j+1].second) - V.begin();
			V.erase(V.begin() + idx);
			dp[i][j] = max(dp[i][j+1], V[idx+1] - V[idx]);
			// printf(" ok %d %d -> %lld\n", i, j, dp[i][j]);
		}
	}

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

	ll ans = INF;
	for (ll i=mn;i<=L;i++) ans = min(ans, solve(i));
	cout << ans << '\n';
}

Compilation message (stderr)

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

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