Submission #1181369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181369		sleepntsheep	Cultivation (JOI17_cultivation)	C++20	0 / 100	1 ms	324 KiB

cultivation

#include<stdio.h>
#include<algorithm>
#include<vector>

int r,c,n,ans=1e9,fup=1e9;
struct pt{int x,y;}p[333];
int main(){
    scanf("%d%d%d",&r,&c,&n);
    for(int i=0;i<n;++i)scanf("%d%d",&p[i].x,&p[i].y),fup=std::min(fup,p[i].x-1);
    std::sort(p,p+n,[](pt&a,pt&b){return a.x-b.x?a.x<b.x:a.y<b.y;});
    std::sort(p,p+n,[](pt&a,pt&b){return a.y-b.y?a.y<b.y:a.x<b.x;});
    n=std::unique(p,p+n,[](pt&a,pt&b){return a.x==b.x&&a.y==b.y;})-p;

    auto CC=[&](int up_plus_dw){
	if(fup>up_plus_dw)return;
	int up=fup,dw=up_plus_dw-fup;

	int lef0=0,rig0=0,gapmax=0,ok=1;
	auto Chk=[&](int i){
	    if(!ok)return;
	    if(i<1)i=1;if(i>r)i=r;
	    std::vector<int>e;
	    for(int j=0;j<n;++j)if((p[j].x>=i&&p[j].x-up<=i)||(p[j].x<=i&&p[j].x+dw>=i))
		e.push_back(p[j].y);
	    if(e.empty()){
		ok=0;
		return;
	    }
	    lef0=std::max(lef0,e[0]-1);
	    rig0=std::max(rig0,c-e.back());
	    for(int i=1;i<(int)e.size();++i)
		gapmax=std::max(gapmax,e[i]-e[i-1]-1);
	};
	for(int i=0;ok&&i<n;++i){
	    Chk(p[i].x-up);
	    Chk(p[i].x-up-1);
	    Chk(p[i].x+dw+1);
	    Chk(p[i].x+dw);
	}
	if(ok)
	    ans=std::min(ans,up+dw+std::max(lef0+rig0,gapmax));
    };

    CC(0);
    for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(p[i].x<p[j].x){
	CC(p[j].x-p[i].x);
    }

    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%d%d%d",&r,&c,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:9:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     for(int i=0;i<n;++i)scanf("%d%d",&p[i].x,&p[i].y),fup=std::min(fup,p[i].x-1);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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