Submission #672193

#	Time	Username	Problem	Language	Result	Execution time	Memory
672193		amunduzbaev	Cultivation (JOI17_cultivation)	C++17	80 / 100	1226 ms	1320 KiB

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];
	} 
	
	if(sz <= 100){
		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);
		set<int> don;
		auto check = [&](int d){
			if(don.count(d)) return;
			don.insert(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 + 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));
					}
				}
			}
		};
		
		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";
	} else {
		vector<int> p(sz);
		iota(p.begin(), p.end(), 0);
		sort(p.begin(), p.end(), [&](int i, int j){
			return y[i] < y[j];
		});
		
		int res = 2 * (n + m);
		for(int u=0;u<n;u++){
			for(int d=0;d<n;d++){
				vector<vector<int>> used(n + 1);
				for(auto i : p){
					int l = max(1ll, x[i] - u), r = min(n, x[i] + d);
					for(int j=l;j<=r;j++){
						used[j].push_back(y[i]);
					}
				}
				
				int mnl = 0, mnr = 0, mn = 0, ok = 1;
				for(int i=1;i<=n;i++){
					if(used[i].empty()){
						ok = 0;
						break;
					}
					mnl = max(mnl, used[i][0] - 1);
					mnr = max(mnr, m - used[i].back());
					for(int j=1;j<(int)used[i].size();j++){
						//~ cout<<i<<" "<<used[i][j]<<" "<<used[i][j-1]<<"\n";
						mn = max(mn, used[i][j] - used[i][j-1] - 1);
					}
				}
				
				if(!ok) continue;
				//~ cout<<u<<" "<<d<<" "<<mnl<<" "<<mnr<<" "<<mn<<"\n";
				res = min(res, u + d + max(mnl + mnr, mn));
			}
		}
		
		cout<<res<<"\n";
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 0 / 20