Submission #671986

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
671986	2022-12-14T14:04:43 Z	amunduzbaev	Cultivation (JOI17_cultivation)	C++17	35 / 100	9 ms	472 KB

cultivation

#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 d){
		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({y[i], id[i]});
			tot.push_back({y[i] + d + 1, -id[i]});
		}
		sort(tot.begin(), tot.end());
		vector<int> v, is;
		vector<ar<int, 3>> Mn;
		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++;
			}
			
			//~ cout<<tot[i][0]<<" : ";
			int mnl = 0, mn = 0;
			int last = -1;
			for(int i=0;i<(int)t.size();i++){
				if(!used[i]) continue;
				if(~last) mn = max(mn, t[i] - t[last] - 1);
				else mnl = t[i] - 1;
				last = i;
			}
			v.push_back(tot[i][0]);
			if(last == -1){
				Mn.push_back({0, 0, 0});
				is.push_back(1);
			} else {
				Mn.push_back({mnl, n - t[last], mn});
				is.push_back(0);
			}
			
			i = j;
		}
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<v[i]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<Mn[i][0]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<Mn[i][1]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<Mn[i][2]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<is[i]<<" ";
		//~ } cout<<"\n";
		
		for(int i=0;i + 1 < (int)v.size();i++){
			int mnl = 0, mnr = 0, mn = 0;
			for(int j=i;j + 1 < (int)v.size();j++){
				if(is[j]) break;
				mnl = max(mnl, Mn[j][0]);
				mnr = max(mnr, Mn[j][1]);
				mn = max(mn, Mn[j][2]);
				if(v[j + 1] - v[i] >= m){
					res = min(res, d + max(mnl + mnr, 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 k=0;k<sz;k++){
			if(y[i] >= y[k]) continue;
			check(y[k] - y[i] - 1);
		}
	}
	
	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	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	224 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	320 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	316 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	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	224 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	320 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	316 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Runtime error	1 ms	472 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	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	224 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	320 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	316 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Runtime error	1 ms	472 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	2 ms	212 KB	Output is correct
2	Correct	7 ms	212 KB	Output is correct
3	Correct	9 ms	452 KB	Output is correct
4	Correct	7 ms	212 KB	Output is correct
5	Correct	7 ms	340 KB	Output is correct
6	Correct	5 ms	216 KB	Output is correct
7	Correct	6 ms	328 KB	Output is correct
8	Correct	7 ms	212 KB	Output is correct
9	Correct	6 ms	212 KB	Output is correct
10	Correct	8 ms	212 KB	Output is correct
11	Correct	7 ms	212 KB	Output is correct
12	Correct	7 ms	212 KB	Output is correct
13	Correct	4 ms	212 KB	Output is correct
14	Correct	5 ms	212 KB	Output is correct
15	Correct	6 ms	212 KB	Output is correct
16	Correct	7 ms	212 KB	Output is correct
17	Correct	7 ms	212 KB	Output is correct
18	Correct	7 ms	212 KB	Output is correct
19	Correct	7 ms	328 KB	Output is correct
20	Correct	7 ms	324 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	212 KB	Output is correct
2	Correct	7 ms	212 KB	Output is correct
3	Correct	9 ms	452 KB	Output is correct
4	Correct	7 ms	212 KB	Output is correct
5	Correct	7 ms	340 KB	Output is correct
6	Correct	5 ms	216 KB	Output is correct
7	Correct	6 ms	328 KB	Output is correct
8	Correct	7 ms	212 KB	Output is correct
9	Correct	6 ms	212 KB	Output is correct
10	Correct	8 ms	212 KB	Output is correct
11	Correct	7 ms	212 KB	Output is correct
12	Correct	7 ms	212 KB	Output is correct
13	Correct	4 ms	212 KB	Output is correct
14	Correct	5 ms	212 KB	Output is correct
15	Correct	6 ms	212 KB	Output is correct
16	Correct	7 ms	212 KB	Output is correct
17	Correct	7 ms	212 KB	Output is correct
18	Correct	7 ms	212 KB	Output is correct
19	Correct	7 ms	328 KB	Output is correct
20	Correct	7 ms	324 KB	Output is correct
21	Runtime error	1 ms	468 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	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	224 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	320 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	316 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Runtime error	1 ms	472 KB	Execution killed with signal 6
19	Halted	0 ms	0 KB	-

Submission #671986

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 30.0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
30.0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0