oj.uz

Submission #1000334

# Submission time Handle Problem Language Result Execution time Memory
1000334 2024-06-17T09:08:18 Z Tob Cultivation (JOI17_cultivation) C++14
30 / 100
 8 ms 3544 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 307, inf = 2e9;

int n, m, k;
int a[N], b[N];
int mem[2*N][N];
pii gr[2*N][N];
vector <int> add[2*N], rem[2*N];

int main () {
	FIO;
	cin >> n >> m >> k;
	
	vector <pii> so;
	for (int i = 0; i < k; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		so.pb({a[i], b[i]});
	}
	sort(all(so));
	for (int i = 0; i < k; i++) {
		a[i] = so[i].F;
		b[i] = so[i].S;
	}
	
	vector <int> v, po;
	int d = a[0];
	for (int i = 0; i < k; i++) a[i] -= d;
	d = n-a[k-1]-1;
	for (int i = 1; i < k; i++) d = max(d, a[i]-a[i-1]-1);
	a[k] = n-1;
	for (int i = 0; i <= k; i++) {
		for (int j = i; j <= k; j++) {
			if (a[j]-a[i] >= d) v.pb(a[j]-a[i]);
			if (a[j]-a[i]-1 >= d) v.pb(a[j]-a[i]-1);
			if (a[i]+n-a[j]-1 >= d) v.pb(a[i]+n-a[j]-1);
			if (a[j]+n-a[i]-1 >= d) v.pb(a[j]+n-a[i]-1);
		}
		if (n-a[i]-1 >= d) v.pb(n-a[i]-1);
	}
	v.pb(d);
	sort(all(v)); v.erase(unique(all(v)), v.end());
	for (int i = 0; i < k; i++) {
		if (a[i]) po.pb(a[i]-1);
		po.pb(a[i]);
	}
	po.pb(n-1);
	sort(all(po)); po.erase(unique(all(po)), po.end());
	
	for (int i = 0; i < 2*N; i++) for (int j = 0; j < N; j++) mem[i][j] = inf;
	for (int i = 0; i < po.size(); i++) {
		set <int> s;
		multiset <int> rj;
		int o = k-1;
		for (int j = 0; j < k; j++) if (a[j] > po[i]) {
			o = j-1;
			break;
		}
		rj.insert(0);
		for (int j = o; j >= 0; j--) {
			mem[i][j] = mem[i][j+1];
			gr[i][j].F = gr[i][j+1].F;
			gr[i][j].S = gr[i][j+1].S;
			if (s.find(b[j]) != s.end()) continue;
			auto p1 = s.lower_bound(b[j]);
			if (p1 == s.end()) {
				if (!s.empty()) rj.insert(b[j]-*(--p1)-1);
				s.insert(b[j]);
				gr[i][j].F = *s.begin();
				gr[i][j].S = m-*s.rbegin()-1;
			}
			else if (p1 == s.begin()) {
				rj.insert(*p1-b[j]-1);
				s.insert(b[j]);
				gr[i][j].F = *s.begin();
				gr[i][j].S = m-*s.rbegin()-1;
			}
			else {
				int x = *p1; --p1; int y = *p1;
				rj.erase(rj.find(x-y-1));
				rj.insert(x-b[j]-1);
				rj.insert(b[j]-y-1);
				s.insert(b[j]);
			}
			mem[i][j] = *rj.rbegin();
		}
	}
	
	int mn = inf, la = po.size()-1;
	for (auto x : v) {
		for (int i = 0, j = 0; i < k; i++) {
			while (j < po.size() && po[j] < a[i]) j++;
			add[j].pb(i);
		}
		for (int i = 0, j = 0; i < k; i++) {
			while (j < po.size() && po[j] < a[i]+x) j++;
			rem[j].pb(i);
		}
		queue <int> q;
		int z;
		vector <int> v1, v2, v3;
		for (int i = 0; i < po.size(); i++) {
			for (auto y : add[i]) q.push(y);
			z = q.front();
			v1.pb(mem[i][z]);
			v2.pb(gr[i][z].F);
			v3.pb(gr[i][z].S);
			if (i != la) for (auto y : rem[i]) q.pop();
			add[i].clear();
			rem[i].clear();
		}
		z = q.front();
		int mx = v1.back(), mxa = v2.back(), mxb = v3.back();
		for (int i = po.size()-2; i >= 0; i--) {
			v1[i] = max(v1[i], v1[i+1]);
			v2[i] = max(v2[i], v2[i+1]);
			v3[i] = max(v3[i], v3[i+1]);
		}
		int re = inf;
		for (int i = 0; i < po.size(); i++) {
			while (po[i]+n-1 > a[z]+x) {
				z++;
				if (z == k) break;
				mx = max(mx, mem[la][z]);
				mxa = max(mxa, gr[la][z].F);
				mxb = max(mxb, gr[la][z].S);
			}
			if (z == k) break;
			re = min(re, max(max(mx, v1[i]), max(mxa, v2[i]) + max(mxb, v3[i])));
		}
		mn = min(mn, re+x);
	}
	
	cout << mn << "\n";

	return 0;
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i = 0; i < po.size(); i++) {
      |                  ~~^~~~~~~~~~~
cultivation.cpp:104:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    while (j < po.size() && po[j] < a[i]) j++;
      |           ~~^~~~~~~~~~~
cultivation.cpp:108:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    while (j < po.size() && po[j] < a[i]+x) j++;
      |           ~~^~~~~~~~~~~
cultivation.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i = 0; i < po.size(); i++) {
      |                   ~~^~~~~~~~~~~
cultivation.cpp:120:27: warning: unused variable 'y' [-Wunused-variable]
  120 |    if (i != la) for (auto y : rem[i]) q.pop();
      |                           ^
cultivation.cpp:132:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for (int i = 0; i < po.size(); i++) {
      |                   ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2536 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 3 ms 2792 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 5 ms 3032 KB Output is correct
25 Correct 3 ms 2780 KB Output is correct
26 Correct 6 ms 3544 KB Output is correct
27 Correct 6 ms 3540 KB Output is correct
28 Correct 3 ms 3032 KB Output is correct
29 Correct 6 ms 3544 KB Output is correct
30 Correct 6 ms 3540 KB Output is correct
31 Correct 6 ms 3540 KB Output is correct
32 Correct 8 ms 3544 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2536 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 3 ms 2792 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 5 ms 3032 KB Output is correct
25 Correct 3 ms 2780 KB Output is correct
26 Correct 6 ms 3544 KB Output is correct
27 Correct 6 ms 3540 KB Output is correct
28 Correct 3 ms 3032 KB Output is correct
29 Correct 6 ms 3544 KB Output is correct
30 Correct 6 ms 3540 KB Output is correct
31 Correct 6 ms 3540 KB Output is correct
32 Correct 8 ms 3544 KB Output is correct
33 Correct 4 ms 3288 KB Output is correct
34 Correct 6 ms 3428 KB Output is correct
35 Correct 7 ms 3540 KB Output is correct
36 Correct 7 ms 3544 KB Output is correct
37 Correct 7 ms 3544 KB Output is correct
38 Correct 8 ms 3412 KB Output is correct
39 Correct 8 ms 3400 KB Output is correct
40 Correct 8 ms 3544 KB Output is correct
41 Correct 4 ms 3300 KB Output is correct
42 Correct 6 ms 3460 KB Output is correct
43 Correct 7 ms 3540 KB Output is correct
44 Correct 7 ms 3432 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2536 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 3 ms 2792 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 5 ms 3032 KB Output is correct
25 Correct 3 ms 2780 KB Output is correct
26 Correct 6 ms 3544 KB Output is correct
27 Correct 6 ms 3540 KB Output is correct
28 Correct 3 ms 3032 KB Output is correct
29 Correct 6 ms 3544 KB Output is correct
30 Correct 6 ms 3540 KB Output is correct
31 Correct 6 ms 3540 KB Output is correct
32 Correct 8 ms 3544 KB Output is correct
33 Correct 4 ms 3288 KB Output is correct
34 Correct 6 ms 3428 KB Output is correct
35 Correct 7 ms 3540 KB Output is correct
36 Correct 7 ms 3544 KB Output is correct
37 Correct 7 ms 3544 KB Output is correct
38 Correct 8 ms 3412 KB Output is correct
39 Correct 8 ms 3400 KB Output is correct
40 Correct 8 ms 3544 KB Output is correct
41 Correct 4 ms 3300 KB Output is correct
42 Correct 6 ms 3460 KB Output is correct
43 Correct 7 ms 3540 KB Output is correct
44 Correct 7 ms 3432 KB Output is correct
45 Correct 1 ms 2648 KB Output is correct
46 Incorrect 2 ms 2648 KB Output isn't correct
47 Halted 0 ms 0 KB -