Submission #1075488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1075488	2024-08-26T07:00:04 Z	qwerasdfzxcl	Cultivation (JOI17_cultivation)	C++17	30 / 100	11 ms	3752 KB

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;

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

	for (auto &x:C) ans = min(ans, solve(x));

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

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%lld %lld", &L, &U);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
cultivation.cpp:59:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  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	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 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	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 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	348 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	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 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	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 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	348 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	600 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	0 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	1372 KB	Output is correct
23	Correct	0 ms	604 KB	Output is correct
24	Correct	4 ms	2352 KB	Output is correct
25	Correct	3 ms	1884 KB	Output is correct
26	Correct	7 ms	3540 KB	Output is correct
27	Correct	7 ms	3540 KB	Output is correct
28	Correct	3 ms	2520 KB	Output is correct
29	Correct	6 ms	3536 KB	Output is correct
30	Correct	6 ms	3540 KB	Output is correct
31	Correct	7 ms	3540 KB	Output is correct
32	Correct	6 ms	3540 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 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	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 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	348 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	600 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	0 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	1372 KB	Output is correct
23	Correct	0 ms	604 KB	Output is correct
24	Correct	4 ms	2352 KB	Output is correct
25	Correct	3 ms	1884 KB	Output is correct
26	Correct	7 ms	3540 KB	Output is correct
27	Correct	7 ms	3540 KB	Output is correct
28	Correct	3 ms	2520 KB	Output is correct
29	Correct	6 ms	3536 KB	Output is correct
30	Correct	6 ms	3540 KB	Output is correct
31	Correct	7 ms	3540 KB	Output is correct
32	Correct	6 ms	3540 KB	Output is correct
33	Correct	10 ms	3536 KB	Output is correct
34	Correct	7 ms	3752 KB	Output is correct
35	Correct	7 ms	3540 KB	Output is correct
36	Correct	7 ms	3536 KB	Output is correct
37	Correct	7 ms	3540 KB	Output is correct
38	Correct	7 ms	3540 KB	Output is correct
39	Correct	7 ms	3540 KB	Output is correct
40	Correct	11 ms	3540 KB	Output is correct
41	Correct	6 ms	3560 KB	Output is correct
42	Correct	6 ms	3540 KB	Output is correct
43	Correct	6 ms	3540 KB	Output is correct
44	Correct	6 ms	3540 KB	Output is correct

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	3 ms	600 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Incorrect	2 ms	600 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	3 ms	600 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Incorrect	2 ms	600 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 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	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 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	348 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	600 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	0 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	1372 KB	Output is correct
23	Correct	0 ms	604 KB	Output is correct
24	Correct	4 ms	2352 KB	Output is correct
25	Correct	3 ms	1884 KB	Output is correct
26	Correct	7 ms	3540 KB	Output is correct
27	Correct	7 ms	3540 KB	Output is correct
28	Correct	3 ms	2520 KB	Output is correct
29	Correct	6 ms	3536 KB	Output is correct
30	Correct	6 ms	3540 KB	Output is correct
31	Correct	7 ms	3540 KB	Output is correct
32	Correct	6 ms	3540 KB	Output is correct
33	Correct	10 ms	3536 KB	Output is correct
34	Correct	7 ms	3752 KB	Output is correct
35	Correct	7 ms	3540 KB	Output is correct
36	Correct	7 ms	3536 KB	Output is correct
37	Correct	7 ms	3540 KB	Output is correct
38	Correct	7 ms	3540 KB	Output is correct
39	Correct	7 ms	3540 KB	Output is correct
40	Correct	11 ms	3540 KB	Output is correct
41	Correct	6 ms	3560 KB	Output is correct
42	Correct	6 ms	3540 KB	Output is correct
43	Correct	6 ms	3540 KB	Output is correct
44	Correct	6 ms	3540 KB	Output is correct
45	Correct	1 ms	604 KB	Output is correct
46	Correct	1 ms	604 KB	Output is correct
47	Correct	2 ms	604 KB	Output is correct
48	Correct	3 ms	600 KB	Output is correct
49	Correct	1 ms	600 KB	Output is correct
50	Correct	1 ms	604 KB	Output is correct
51	Correct	1 ms	604 KB	Output is correct
52	Correct	2 ms	604 KB	Output is correct
53	Correct	1 ms	604 KB	Output is correct
54	Incorrect	2 ms	600 KB	Output isn't correct
55	Halted	0 ms	0 KB	-

Submission #1075488

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0