Submission #105833

#	Time	Username	Problem	Language	Result	Execution time	Memory
105833		Pro_ktmr	Cultivation (JOI17_cultivation)	C++14	30 / 100	526 ms	816 KiB

cultivation

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP(a,b) make_pair(a,b)
LL W,H;
int N;
LL y[300],x[300];
int main(){
	cin >> W >> H >> N;
	if(W > 40) return -1;
	for(int i=0; i<N; i++){
		cin >> x[i] >> y[i];
		x[i]--; y[i]--;
	}
	
	LL ans = LLONG_MAX;
	for(LL l=0; l<=40; l++){
		for(LL r=0; r<=40; r++){
			vector<LL> memo[40];
			for(int i=0; i<N; i++){
				for(LL j=max(0LL,x[i]-l); j<=min(W-1,x[i]+r); j++) memo[j].push_back(y[i]);
			}
			LL u = 0;
			LL d = 0;
			LL tmp = 0;
			for(LL i=0; i<W; i++){
				sort(memo[i].begin(), memo[i].end());
				if(memo[i].size() == 0){
					tmp = LLONG_MAX-100;
					break;
				}
				u = max(u, memo[i][0]);
				d = max(d, H-memo[i].back()-1);
				for(int j=1; j<memo[i].size(); j++){
					tmp = max(tmp, memo[i][j] - memo[i][j-1] - 1);
				}
			}
			ans = min(ans, l+r+max(u+d,tmp));
		}
	}
	cout << ans << endl;
	
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=1; j<memo[i].size(); j++){
                  ~^~~~~~~~~~~~~~~

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