Submission #671841

#	Time	Username	Problem	Language	Result	Execution time	Memory
671841		amunduzbaev	Cultivation (JOI17_cultivation)	C++17	30 / 100	107 ms	596 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);
	for(int i=0;i<sz;i++){
		cin >> x[i] >> y[i];
	}
	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: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20