Submission #27828

#	Time	Username	Problem	Language	Result	Execution time	Memory
27828		suhgyuho_william	Cultivation (JOI17_cultivation)	C++14	30 / 100	2000 ms	3652 KiB

cultivation

#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define left leftt
#define right rightt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007LL

using namespace std;

int N; lld R,C,ans;
struct data{
	lld x,y;
}a[302];
multiset<lld> S;

void process(lld l,lld r){
	lld ly,ry,lry;
	ly = ry = lry = 0;

	vector<pll> tmp;
	for(int i=1; i<=N; i++){
		tmp.pb({max((lld)1,a[i].x-l),a[i].y});
		tmp.pb({min(R,a[i].x+r)+1,-a[i].y});
	}
	sort(tmp.begin(),tmp.end());
	if(tmp[0].first != 1 || tmp.back().first != R+1) return;
	for(int i=0; i<tmp.size(); i++){
        int e;
        for(int j=i; j<tmp.size(); j++){
            if(tmp[i].first != tmp[j].first) break;
            e = j;
        }
        for(int j=i; j<=e; j++){
            if(tmp[j].second > 0) S.insert(tmp[j].second);
            else S.erase(S.find(-tmp[j].second));
        }
        if(S.empty() && tmp[i].first <= R) return;
        if(S.empty()) break;
        auto it = S.end(); it--;
        ly = max(ly,*S.begin()-1);
        ry = max(ry,C-(*it));
        lld bef;
        for(it = S.begin(); it != S.end(); it++){
            if(it == S.begin()){
                bef = *it;
                continue;
            }
            lry = max(lry,*it-bef-1);
            bef = *it;
        }
        i = e;
	}
	if(ly > ry) swap(ly,ry);
	if(ly+ry < lry){
		ry = lry-ly;
	}
	ans = min(ans,l+r+ly+ry);
}

int main(){
    //freopen("input.txt","r",stdin);
	scanf("%lld %lld %d",&R,&C,&N);
	for(int i=1; i<=N; i++){
		scanf("%d %d",&a[i].x,&a[i].y);
	}
	sort(a+1,a+N+1,[&](data &x,data &y){
		return x.x < y.x;
	});
	ans = Linf;
	vector<int> X;
	a[N+1].x = R+1;
	for(int i=0; i<=N; i++){
        for(int j=i; j<=N+1; j++){
            X.pb(a[j].x-a[i].x);
            X.pb(a[j].x-a[i].x+1);
            X.pb(max((lld)0,a[j].x-a[i].x-1));
        }
	}
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	for(auto &i : X){
		for(auto &j : X){
			process(i,j);
		}
	}
	process(3,0);
	printf("%lld\n",ans);

	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'void process(long long int, long long int)':
cultivation.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<tmp.size(); i++){
                ^
cultivation.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i; j<tmp.size(); j++){
                       ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:70:32: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d %d",&a[i].x,&a[i].y);
                                ^
cultivation.cpp:70:32: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
cultivation.cpp:68:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %d",&R,&C,&N);
                                ^
cultivation.cpp:70:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].x,&a[i].y);
                                 ^
cultivation.cpp: In function 'void process(long long int, long long int)':
cultivation.cpp:39:23: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
         for(int j=i; j<=e; 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