Submission #367945

#	Time	Username	Problem	Language	Result	Execution time	Memory
367945		denkendoemeer	Cultivation (JOI17_cultivation)	C++14	100 / 100	180 ms	2536 KiB

cultivation

#include<bits/stdc++.h>
typedef long long ll;
#define inf (0x3f3f3f3f)
using namespace std;
vector<int>gx[305],gu[305],gd[305],gs[305];
int vu[90005],vd[90005],vs[90005];
vector<int>aux,aux2,v2;
int a[305],b[305];
int h,w,n,k,l,ans=inf*2;
void calc(vector<pair<int,int>>&auxi,vector<int>&x,vector<int>&u,vector<int>&d,vector<int>&s)
{
    sort(auxi.begin(),auxi.end());
	multiset<int> st1,st2;
	st1.insert(0);
	st1.insert(h+1);
	st2.insert(h+1);
	int i,j,n=auxi.size(),px,py,k;
    for(i=0;i<n;i=j){
		px=auxi[i].first;
		for(j=i+1;j<n && auxi[j].first==px;j++);
		for(k=i;k<j;k++){
			py=auxi[k].second;
			auto it=st1.insert(py);
			if (st1.begin()!=it && st1.end()!=next(it))
				st2.erase(st2.find(*next(it)-*prev(it)));
			if (st1.begin()!=it)
                st2.insert(py-*prev(it));
			if (st1.end()!=next(it))
                st2.insert(*next(it)-py);
		}
		x.push_back(px);
		s.push_back(*prev(st2.end())-1);
		u.push_back(*next(st1.begin())-1);
		d.push_back(h-*prev(prev(st1.end())));
	}
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d%d%d",&h,&w,&n);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        aux.push_back(b[i]-1);
        if (b[i]>1)
            aux2.push_back(b[i]-1);
    }
    sort(aux.begin(),aux.end());
    sort(aux2.begin(),aux2.end());
    aux.erase(unique(aux.begin(),aux.end()),aux.end());
    aux2.erase(unique(aux2.begin(),aux2.end()),aux2.end());
    k=aux2.size();
    aux2.push_back(w);
    int x,j,num;
    for(i=0;i<=k;i++){
        x=aux2[i];
        vector<pair<int,int>>auxi;
        for(j=1;j<=n;j++){
            num=x-b[j];
            if (num>=0){
                auxi.push_back(make_pair(num,a[j]));
                v2.push_back(num);
            }
        }
        calc(auxi,gx[i],gu[i],gd[i],gs[i]);
    }
    sort(v2.begin(),v2.end());
    v2.erase(unique(v2.begin(),v2.end()),v2.end());
    l=v2.size();
    j=k-1;
    int lx,i2,j2;
    for(i=aux.size();i--;){
        lx=aux[i];
        for(;j>=0 && lx<aux2[j];j--){
            j2=0;
            int n=gx[j].size(),x;
            for(i2=0;i2<l;i2++){
                x=v2[i2];
                if (j2<n && gx[j][j2]<=x)
                    j2++;
                if (j2){
                    vu[i2]=max(vu[i2],gu[j][j2-1]);
                    vd[i2]=max(vd[i2],gd[j][j2-1]);
                    vs[i2]=max(vs[i2],gs[j][j2-1]);
                }
                else
                    vu[i2]=vd[i2]=vs[i2]=inf;
            }
        }
        int n=gx[k].size(),rx,du,dd,ds;
        for(i2=0,j2=0;i2<l || j2<n;){
            rx=inf;
            if (i2<l)
                rx=v2[i2]-lx;
            if (j2<n)
                rx=min(rx,gx[k][j2]);
            if (rx<0){
                i2++;
                continue;
            }
            if (i2<l && v2[i2]-lx==rx)
                i2++;
            if (j2<n && gx[k][j2]==rx)
                j2++;
            if (i2==0 || j2==0)
                continue;
            du=max(vu[i2-1],gu[k][j2-1]);
            dd=max(vd[i2-1],gd[k][j2-1]);
            ds=max(vs[i2-1],gs[k][j2-1]);
            ll rez=ll(max(ds,du+dd))+lx+rx;
            if (ans>rez)
                ans=rez;
        }
    }
    printf("%d\n",ans);
return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d%d%d",&h,&w,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         scanf("%d%d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

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