Submission #560489

#	Time	Username	Problem	Language	Result	Execution time	Memory
560489		amunduzbaev	Cultivation (JOI17_cultivation)	C++17	5 / 100	1713 ms	262144 KiB

cultivation

#include "bits/stdc++.h"
using namespace std;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int R, C; cin>>R>>C;
	int n; cin>>n;
	vector<int> x(n), y(n);
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	
	auto check = [&](int a, int c, int b, int d){
		vector<vector<int>> g(R + 1, vector<int>(C + 1));
		for(int i=0;i<n;i++){
			int lx = max(1, x[i] - a), rx = min(R, x[i] + c), ly = max(1, y[i] - b), ry = min(C, y[i] + d);
			g[lx][ly]++;
			if(ry < C) g[lx][ry+1]--;
			if(rx < R) g[rx+1][ly]--;
			if(rx < R && ry < C) g[rx+1][ry+1]++;
		}
		
		for(int i=1;i<=R;i++){
			for(int j=1;j<=C;j++){
				g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
				if(!g[i][j]) return false;
			}
		}
		
		return true;
	};
	
	int res = R + C;
	for(int a=0;a<R;a++){
		for(int b=0;b<C;b++){
			for(int c=0;a+c<R;c++){
				for(int d=0;b+d<C;d++){
					if(check(a, c, b, d)) res = min(res, a + b + c + d);
				}
			}
		}
	}
	
	cout<<res<<"\n";
}

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