Submission #113863

#	Time	Username	Problem	Language	Result	Execution time	Memory
113863		Bruteforceman	Cultivation (JOI17_cultivation)	C++11	15 / 100	2069 ms	512 KiB

cultivation

#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
 
int R, C;
int x[305], y[305];
int n;
const int inf = 2e9 + 7;
 
long long getOpt(int len) {	
	// cout << len << endl;
	int mnX = inf;
	int mxX = -inf;
	for(int i = 1; i <= n; i++) {
		mnX = min(mnX, x[i]);
		mxX = max(mxX, x[i] + len);
	}
	set <pii> endp;
	map <int, int> com;
	for(int i = 1; i <= n; i++) {
		int l = x[i];
		int r = x[i] + len;
		endp.insert(pii(l - 1, 1));
		endp.insert(pii(r + 1, -1));
		endp.insert(pii(l, -1));
		endp.insert(pii(r, 1));
	} 
	vector <pii> v (endp.begin(), endp.end());
	vector <int> sz, val, up, down;
 
	// for(int i = 0; i < v.size(); i++) {
	// 	cout << v[i].first << ' ' << v[i].second << endl;
	// }
	assert(v.size() % 2 == 0);

	for(int i = 2; i < v.size(); i += 2) {
		int l = v[i - 1].first;
		int r = v[i].first;
		vector <int> can;
		for(int j = 1; j <= n; j++) {
			int p = x[j];
			int q = x[j] + len;
			if(p <= l && r <= q) {
				can.push_back(y[j]);
			}
		}
		sort(can.begin(), can.end());
		sz.push_back(r - l + 1);
		if(can.empty()) {
			val.push_back(inf);
			up.push_back(inf);
			down.push_back(inf);
		} else {
			int diff = 0;
			for(int k = 1; k < can.size(); k++) {
				diff = max(diff, can[k] - can[k - 1] - 1);
			}
			val.push_back(diff);
			up.push_back(can.front() - 1);
			down.push_back(C - can.back());
		}
	}
	// for(int i = 0; i < sz.size(); i++) {
	// 	cout << sz[i] << ' ' << val[i] << ' ' << up[i] << ' ' << down[i] << endl;
	// }
	multiset <long long> cont, upC, downC;
	int r = 0;
	int sum = 0;
	int prev = 0;
	long long ans = inf;
	for(int i = 0; i < sz.size(); i++) {
		if(prev > len + 1) break;
		while(r < sz.size() && sum < R) {
			sum += sz[r];
			cont.insert(val[r]);
			upC.insert(up[r]);
			downC.insert(down[r]);
			++r;
		}
		if(sum >= R) {
			ans = min(ans, max(*upC.rbegin() + *downC.rbegin(), *cont.rbegin()));
		}
		prev += sz[i];
		sum -= sz[i];
		cont.erase(cont.find(val[i]));
		upC.erase(upC.find(up[i]));
		downC.erase(downC.find(down[i]));
	} 
	return ans;
}
 
int main(int argc, char const *argv[])
{
	scanf("%d %d", &R, &C);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &x[i], &y[i]);
	}	
	long long ans = getOpt(0);
	// for(int i = 1; i <= n; i++) {
	// 	for(int j = i; j <= n; j++) {
	// 		int dif = abs(x[j] - x[i]) - 1;
	// 		if(dif >= 0) {
	// 			ans = min(ans, getOpt(dif) + dif);
	// 		}
	// 		dif = R - abs(x[j] - x[i]) - 1;
	// 		if(dif >= 0) {
	// 			ans = min(ans, getOpt(dif) + dif);
	// 		}
	// 	}
	// }
	for(int i = 0; i <= R+C; i++) {
		ans = min(ans, i + getOpt(i));
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'long long int getOpt(int)':
cultivation.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < v.size(); i += 2) {
                 ~~^~~~~~~~~~
cultivation.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 1; k < can.size(); k++) {
                   ~~^~~~~~~~~~~~
cultivation.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < sz.size(); i++) {
                 ~~^~~~~~~~~~~
cultivation.cpp:73:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(r < sz.size() && sum < R) {
         ~~^~~~~~~~~~~
cultivation.cpp: In function 'int main(int, const char**)':
cultivation.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &R, &C);
  ~~~~~^~~~~~~~~~~~~~~~~
cultivation.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
cultivation.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x[i], &y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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