Submission #113859

#	Time	Username	Problem	Language	Result	Execution time	Memory
113859		Bruteforceman	Cultivation (JOI17_cultivation)	C++11	5 / 100	2047 ms	476 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]));
			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);
    			}
    		}
    	}
    	printf("%lld\n", ans);
    	return 0;
    }

Compilation message (stderr)

cultivation.cpp: In function 'long long int getOpt(int)':
cultivation.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 1; i < v.size(); i += 2) {
                     ~~^~~~~~~~~~
cultivation.cpp:126:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < sz.size(); i++) {
                     ~~^~~~~~~~~~~
cultivation.cpp:128:15: 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:149:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d", &R, &C);
      ~~~~~^~~~~~~~~~~~~~~~~
cultivation.cpp:150:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &n);
      ~~~~~^~~~~~~~~~
cultivation.cpp:152:12: 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