Submission #1226492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226492		PenguinsAreCute	Cultivation (JOI17_cultivation)	C++17	5 / 100	2092 ms	327680 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, x0, y0;
	cin >> x0 >> y0 >> n;
	int a[n], b[n];
	for(int i=0;i<n;i++) {
		cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
	}
	int ans = 2e9;
	for(int west=0;west<x0;west++)
		for(int east=0;east<x0;east++)
			for(int north=0;north<y0;north++)
				for(int south=0;south<y0;south++) {
					int gr[x0+1][y0+1];
					memset(gr,0,sizeof(gr));
					for(int i=0;i<n;i++) {
						gr[max(a[i]-west,0)][max(b[i]-south,0)]++;
						gr[max(a[i]-west,0)][min(b[i]+north+1,y0)]--;
						gr[min(a[i]+east+1,x0)][max(b[i]-south,0)]--;
						gr[min(a[i]+east+1,x0)][min(b[i]+north+1,y0)]++;
					}
					for(int i=0;i<x0;i++)
						for(int j=0;j<y0-1;j++)
							gr[i][j+1]+=gr[i][j];
					for(int i=0;i<x0-1;i++)
						for(int j=0;j<y0;j++)
							gr[i+1][j]+=gr[i][j];
					bool val = 1;
					for(int i=0;i<x0;i++)
						for(int j=0;j<y0;j++)
							if(!gr[i][j])
								val = 0;
					if(val)
						ans = min(ans, north+south+east+west);
				}
	cout << ans;
}

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