oj.uz

Submission #55272

# Submission time Handle Problem Language Result Execution time Memory
55272 2018-07-06T21:05:14 Z ksun48 Cultivation (JOI17_cultivation) C++14
35 / 100
 2000 ms 920 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;;

LL r, c, n;
vector<pair<LL,LL> > seeds;
const LL INF = 2100100100;
LL best = INF;
set<pair<LL,LL> > tried;
void tryx(LL x, LL startx){
	if(x < 0 || tried.find({x,startx}) != tried.end()){
		return;
	}
	LL endx = startx + r - 1;
	// insert z.second at time z.first
	// delete at time z.first + x + 1


	map<LL, vector<pair<LL, LL> > > events;
	for(pair<LL,LL> z : seeds){
		if(z.first + x < startx || z.first > endx) continue;
		events[max(z.first, startx)].push_back({0, z.second}); // ins
		events[min(z.first + x, endx) + 1].push_back({1, z.second}); // del
	}

	LL maxup = 0;
	LL maxdown = 0;
	LL maxtot = 0;

	multiset<LL> grass;
	grass.insert(-1);
	grass.insert(c);
	multiset<LL> diffs;
	diffs.insert(c+1);
	for(auto x : events){
		for(pair<LL,LL> event : x.second){
			LL a = event.second;
			if(event.first == 0){
				grass.insert(a);
			}
			LL a1 = *(--grass.find(a));
			LL a2 = *(++grass.find(a));
			if(event.first == 0){
				diffs.erase(diffs.find(a2-a1));
				diffs.insert(a-a1);
				diffs.insert(a2-a);
			} else if(event.first == 1){
				diffs.erase(diffs.find(a-a1));
				diffs.erase(diffs.find(a2-a));
				diffs.insert(a2-a1);
			}
			if(event.first == 1){
				grass.erase(grass.find(a));
			}
		}
		if(x.first > endx){
			break;
		}
		maxtot = max(maxtot, *(--diffs.end()) );
		maxup = max(maxup, *(++grass.begin()) - 0);
		maxdown = max(maxdown, c-1 - *(--(--grass.end())) );
	}
	if(maxtot == c + 1){
		return;
	}
	best = min(best, max(maxup + maxdown, maxtot - 1) + x);
}
int main(){
	cin >> r >> c >> n;
	for(LL i = 0; i < n; i++){
		LL s, e;
		cin >> s >> e;
		s--; e--;
		seeds.push_back({s,e});
	}
	sort(seeds.begin(), seeds.end());
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			tryx(seeds[i].first + r-1 - seeds[j].first, seeds[i].first);
		}
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				tryx(seeds[j].first - 1 - seeds[k].first, seeds[i].first);
			}
		}
	}		
	cout << best << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 11 ms 460 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 560 KB Output is correct
11 Correct 2 ms 560 KB Output is correct
12 Correct 2 ms 560 KB Output is correct
13 Correct 2 ms 560 KB Output is correct
14 Correct 3 ms 560 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 3 ms 560 KB Output is correct
17 Correct 44 ms 596 KB Output is correct
18 Execution timed out 2062 ms 596 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 11 ms 460 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 560 KB Output is correct
11 Correct 2 ms 560 KB Output is correct
12 Correct 2 ms 560 KB Output is correct
13 Correct 2 ms 560 KB Output is correct
14 Correct 3 ms 560 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 3 ms 560 KB Output is correct
17 Correct 44 ms 596 KB Output is correct
18 Execution timed out 2062 ms 596 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 596 KB Output is correct
2 Correct 127 ms 620 KB Output is correct
3 Correct 150 ms 652 KB Output is correct
4 Correct 130 ms 788 KB Output is correct
5 Correct 132 ms 824 KB Output is correct
6 Correct 161 ms 824 KB Output is correct
7 Correct 97 ms 824 KB Output is correct
8 Correct 134 ms 824 KB Output is correct
9 Correct 95 ms 824 KB Output is correct
10 Correct 136 ms 824 KB Output is correct
11 Correct 145 ms 824 KB Output is correct
12 Correct 138 ms 824 KB Output is correct
13 Correct 108 ms 824 KB Output is correct
14 Correct 121 ms 824 KB Output is correct
15 Correct 183 ms 824 KB Output is correct
16 Correct 140 ms 824 KB Output is correct
17 Correct 139 ms 824 KB Output is correct
18 Correct 167 ms 824 KB Output is correct
19 Correct 164 ms 824 KB Output is correct
20 Correct 131 ms 824 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 596 KB Output is correct
2 Correct 127 ms 620 KB Output is correct
3 Correct 150 ms 652 KB Output is correct
4 Correct 130 ms 788 KB Output is correct
5 Correct 132 ms 824 KB Output is correct
6 Correct 161 ms 824 KB Output is correct
7 Correct 97 ms 824 KB Output is correct
8 Correct 134 ms 824 KB Output is correct
9 Correct 95 ms 824 KB Output is correct
10 Correct 136 ms 824 KB Output is correct
11 Correct 145 ms 824 KB Output is correct
12 Correct 138 ms 824 KB Output is correct
13 Correct 108 ms 824 KB Output is correct
14 Correct 121 ms 824 KB Output is correct
15 Correct 183 ms 824 KB Output is correct
16 Correct 140 ms 824 KB Output is correct
17 Correct 139 ms 824 KB Output is correct
18 Correct 167 ms 824 KB Output is correct
19 Correct 164 ms 824 KB Output is correct
20 Correct 131 ms 824 KB Output is correct
21 Execution timed out 2063 ms 920 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 11 ms 460 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 560 KB Output is correct
11 Correct 2 ms 560 KB Output is correct
12 Correct 2 ms 560 KB Output is correct
13 Correct 2 ms 560 KB Output is correct
14 Correct 3 ms 560 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 3 ms 560 KB Output is correct
17 Correct 44 ms 596 KB Output is correct
18 Execution timed out 2062 ms 596 KB Time limit exceeded
19 Halted 0 ms 0 KB -