oj.uz

Submission #671971

# Submission time Handle Problem Language Result Execution time Memory
671971 2022-12-14T13:36:33 Z amunduzbaev Cultivation (JOI17_cultivation) C++17
35 / 100
 14 ms 444 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin >> n >> m;
	int sz; cin >> sz;
	vector<int> x(sz), y(sz), t;
	for(int i=0;i<sz;i++){
		cin >> x[i] >> y[i];
	} 
	assert(sz <= 25);
	
	t = x;
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	vector<int> used(t.size());
	
	vector<int> id(sz);
	for(int i=0;i<sz;i++){
		id[i] = lower_bound(t.begin(), t.end(), x[i]) - t.begin() + 1;
	}
	
	int res = 2 * (n + m);
	auto check = [&](int w, int e){
		vector<ar<int, 2>> tot;
		for(int i=0;i<sz;i++){
			//~ cout<<max(1LL, y[i] - w)<<" "<<min(y[i] + e, m)<<"\n";
			tot.push_back({max(1LL, y[i] - w), id[i]});
			tot.push_back({min(y[i] + e, m) + 1, -id[i]});
			
		}
		sort(tot.begin(), tot.end());
		if(tot[0][0] > 1 || tot.back()[0] <= m) return;
		//~ cout<<w<<" "<<e<<"\n";
		int mnl = 0, mnr = 0, mn = 0;
		//~ for(auto x : tot){
			//~ cout<<x[0]<<" "<<x[1]<<"\n";
		//~ } cout<<"\n";
		for(int i=0;i<(int)tot.size();){
			int j = i;
			while(j < (int)tot.size() && tot[j][0] == tot[i][0]){
				if(tot[j][1] > 0) used[tot[j][1] - 1]++;
				else used[-tot[j][1] - 1]--;
				j++;
			}
			
			if(tot[i][0] == m + 1){
				break;
			}
			
			//~ cout<<tot[i][0]<<" : ";
			int last = -1;
			for(int i=0;i<(int)t.size();i++){
				if(!used[i]) continue;
				//~ cout<<t[i]<<" ";
				if(~last) mn = max(mn, t[i] - t[last] - 1);
				else mnl = max(mnl, t[i] - 1);
				last = i;
			}
			//~ cout<<"\n";
			//~ cout<<mn<<"\n";
			if(last == -1) return;
			mnr = max(mnr, n - t[last]);
			
			i = j;
		}
		
		//~ cout<<w<<" "<<e<<" "<<mnl<<" "<<mnr<<" "<<mn<<"\n";
		res = min(res, w + e + max(mnr + mnl, mn));
	};
	
	//~ check(3, 1);
	
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++){
			check(y[i] - 1, m - y[j]);
		}
		
		for(int j=0;j<sz;j++){
			for(int k=0;k<sz;k++){
				if(y[j] + y[i] > y[k]) continue;
				check(y[i] - 1, y[k] - y[j] - y[i]);
			}
		}
	}
	
	cout<<res<<"\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 4 ms 212 KB Output is correct
18 Runtime error 1 ms 444 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 4 ms 212 KB Output is correct
18 Runtime error 1 ms 444 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 8 ms 212 KB Output is correct
3 Correct 11 ms 212 KB Output is correct
4 Correct 12 ms 320 KB Output is correct
5 Correct 12 ms 316 KB Output is correct
6 Correct 11 ms 212 KB Output is correct
7 Correct 10 ms 212 KB Output is correct
8 Correct 3 ms 328 KB Output is correct
9 Correct 3 ms 328 KB Output is correct
10 Correct 9 ms 212 KB Output is correct
11 Correct 11 ms 212 KB Output is correct
12 Correct 11 ms 316 KB Output is correct
13 Correct 5 ms 212 KB Output is correct
14 Correct 11 ms 324 KB Output is correct
15 Correct 2 ms 212 KB Output is correct
16 Correct 14 ms 324 KB Output is correct
17 Correct 12 ms 324 KB Output is correct
18 Correct 8 ms 320 KB Output is correct
19 Correct 14 ms 320 KB Output is correct
20 Correct 3 ms 212 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 8 ms 212 KB Output is correct
3 Correct 11 ms 212 KB Output is correct
4 Correct 12 ms 320 KB Output is correct
5 Correct 12 ms 316 KB Output is correct
6 Correct 11 ms 212 KB Output is correct
7 Correct 10 ms 212 KB Output is correct
8 Correct 3 ms 328 KB Output is correct
9 Correct 3 ms 328 KB Output is correct
10 Correct 9 ms 212 KB Output is correct
11 Correct 11 ms 212 KB Output is correct
12 Correct 11 ms 316 KB Output is correct
13 Correct 5 ms 212 KB Output is correct
14 Correct 11 ms 324 KB Output is correct
15 Correct 2 ms 212 KB Output is correct
16 Correct 14 ms 324 KB Output is correct
17 Correct 12 ms 324 KB Output is correct
18 Correct 8 ms 320 KB Output is correct
19 Correct 14 ms 320 KB Output is correct
20 Correct 3 ms 212 KB Output is correct
21 Runtime error 1 ms 440 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 4 ms 212 KB Output is correct
18 Runtime error 1 ms 444 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -