oj.uz

Submission #1075472

# Submission time Handle Problem Language Result Execution time Memory
1075472 2024-08-26T06:47:10 Z qwerasdfzxcl Cultivation (JOI17_cultivation) C++17
15 / 100
 2000 ms 4756 KB 
#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;

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

	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] - 1);
		FUCK[0][i][n] = V[1] - V[0] - 1;
		FUCK[1][i][n] = V.back() - (*++V.rbegin()) - 1;

		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] - V[idx-1] - 1);
			FUCK[0][i][j] = V[1] - V[0] - 1;
			FUCK[1][i][j] = V.back() - (*++V.rbegin()) - 1;
		}
	}

	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 (a[j]-a[i]+1 >= mn) C.push_back(a[j]-a[i]+1);
			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());

	for (auto &x:C) ans = min(ans, solve(x));
	for (int i=mn;i<=L;i++) ans = min(ans, solve(i));

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

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 2 ms 1628 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 4 ms 2520 KB Output is correct
25 Correct 3 ms 1884 KB Output is correct
26 Correct 9 ms 4560 KB Output is correct
27 Correct 9 ms 4560 KB Output is correct
28 Correct 5 ms 2440 KB Output is correct
29 Correct 8 ms 4560 KB Output is correct
30 Correct 9 ms 4560 KB Output is correct
31 Correct 11 ms 4756 KB Output is correct
32 Correct 9 ms 4556 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 2 ms 1628 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 4 ms 2520 KB Output is correct
25 Correct 3 ms 1884 KB Output is correct
26 Correct 9 ms 4560 KB Output is correct
27 Correct 9 ms 4560 KB Output is correct
28 Correct 5 ms 2440 KB Output is correct
29 Correct 8 ms 4560 KB Output is correct
30 Correct 9 ms 4560 KB Output is correct
31 Correct 11 ms 4756 KB Output is correct
32 Correct 9 ms 4556 KB Output is correct
33 Incorrect 6 ms 3540 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 2 ms 1628 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 4 ms 2520 KB Output is correct
25 Correct 3 ms 1884 KB Output is correct
26 Correct 9 ms 4560 KB Output is correct
27 Correct 9 ms 4560 KB Output is correct
28 Correct 5 ms 2440 KB Output is correct
29 Correct 8 ms 4560 KB Output is correct
30 Correct 9 ms 4560 KB Output is correct
31 Correct 11 ms 4756 KB Output is correct
32 Correct 9 ms 4556 KB Output is correct
33 Incorrect 6 ms 3540 KB Output isn't correct
34 Halted 0 ms 0 KB -