Submission #113854

#	Time	Username	Problem	Language	Result	Execution time	Memory
113854		Bruteforceman	Cultivation (JOI17_cultivation)	C++11	5 / 100	12 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 = 1e9 + 7;
vector <int> beg[605], fin[605];

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;
		if(l > mnX) {
			endp.insert(pii(l - 1, 1));
		}
		if(r < mxX) {
			endp.insert(pii(r + 1, -1));
		}
		endp.insert(pii(l, -1));
		endp.insert(pii(r, 1));
		com[l]; com[r];
	} 
	vector <pii> v (endp.begin(), endp.end());
	int idx = 0;
	for(auto &i : com) {
		i.second = ++idx;
	}
	for(int i = 0; i <= idx; i++) {
		beg[i].clear(); fin[i].clear();
	}
	for(int i = 1; i <= n; i++) {
		int l = x[i];
		int r = x[i] + len;
		beg[com[l]].push_back(i);
		fin[com[r]].push_back(i);
	}
	multiset <int> s;
	multiset <int> diff;
	vector <int> sz, val, up, down;

	for(int i = 1; i < v.size(); i += 2) {
		int l = v[i - 1].first;
		int r = v[i].first;
		int cmpL = com[l];
		int cmpR = com[r];
		for(auto j : beg[cmpL]) {
			s.insert(y[j]);
			auto it = s.lower_bound(y[j]);
			int prev = -1;
			int nxt = -1;
			if(it != s.begin()) {
				prev = *(--it);
				++it;
			}
			++it;
			if(it != s.end()) {
				nxt = *it;
			}
			if(prev != -1) {
				diff.insert(y[j] - prev);
			}
			if(nxt != -1) {
				diff.insert(nxt - y[j]);
			}
			if(prev != -1 && nxt != -1) {
				diff.erase(diff.find(nxt - prev));
			}
		}
		sz.push_back(r - l + 1);
		if(s.empty()) {
			val.push_back(inf);
			up.push_back(inf);
			down.push_back(inf);
		} else {
			int opt;
			if(!diff.empty()) {
				opt = *diff.rbegin() - 1;
			} else opt = 0;
			val.push_back(opt);
			up.push_back(*s.begin() - 1);
			down.push_back(C - *s.rbegin());
		}
		for(auto j : fin[cmpR]) {
			auto it = s.lower_bound(y[j]);
			int prev = -1;
			int nxt = -1;
			if(it != s.begin()) {
				prev = *(--it);
				++it;
			}
			++it;
			if(it != s.end()) {
				nxt = *it;
			}
			if(prev != -1) {
				diff.erase(diff.find(y[j] - prev));
			}
			if(nxt != -1) {
				diff.erase(diff.find(nxt - y[j]));
			}
			if(prev != -1 && nxt != -1) {
				diff.insert(nxt - prev);
			}
			s.erase(s.find(y[j]));
		}
	}
	// for(int i = 0; i < sz.size(); i++) {
	// 	cout << sz[i] << ' ' << val[i] << ' ' << up[i] << ' ' << down[i] << endl;
	// }
	multiset <int> cont, upC, downC;
	int r = 0;
	int sum = 0;
	int prev = 0;
	int 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]));
	} 
	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);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'long long int getOpt(int)':
cultivation.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < v.size(); i += 2) {
                 ~~^~~~~~~~~~
cultivation.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < sz.size(); i++) {
                 ~~^~~~~~~~~~~
cultivation.cpp:128: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:147: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:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
cultivation.cpp:150: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: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20