Submission #931373

#	Time	Username	Problem	Language	Result	Execution time	Memory
931373		De3b0o	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	1 ms	348 KiB

joioi

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define er erase
#define pb push_back
#define ppb pop_back()
#define ph push
#define pp pop()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid (l+r)/2

using namespace std;

int main()
{
    //d3
    ll h , w;
    cin >> h >> w;
    ll a[h][w];
    for(int i = 0 ; h>i ; i++)
        for(int j = 0 ; w>j ; j++)
            cin >> a[i][j];
    ll ans[h][w];
    pair<pll,pll> b[h][w];
    pll mnmx[w+1];
    ll pmx = 0 , pmn = 1e10;
    mnmx[w].F=1e10;
    mnmx[w].S=0;
    for(int i = w-1 ; i>=0 ; i--)
    {
        ll mn = 1e10 , mx = 0;
        for(int j = 0 ; h>j ; j++)
        {
            mn=min(mn,a[j][i]);
            mx=max(mx,a[j][i]);
        }
        mnmx[i].F=min(mn,pmn);
        mnmx[i].S=max(mx,pmx);
        pmn=mnmx[i].F;
        pmx=mnmx[i].S;
    }
    multiset<ll> fc;
    multiset<ll> fcc;
    for(int i = 0 ; h>i ; i++)
        fc.in(a[i][0]);
    for(int i = 0 ; h>i ; i++)
    {
        fc.erase(fc.find(a[i][0]));
        fcc.in(a[i][0]);
        auto it = fcc.begin();
        ll mn = *it;
        it = fcc.end();
        it--;
        ll mx = *it;
        ans[i][0]=mx-mn;
        b[i][0].F.F=mn;
        b[i][0].F.S=mx;
        mn = mnmx[1].F;
        mx = mnmx[1].S;
        b[i][0].S.F=1e10;
        b[i][0].S.S=0;
        if(fc.size())
        {
            it = fc.begin();
            b[i][0].S.F=*it;
            mn=min(mn,*it);
            it = fc.end();
            it--;
            b[i][0].S.S=*it;
            mx=max(mx,*it);
        }
        ans[i][0] = max(ans[i][0],mx-mn);
    }
    //for(int i = 0 ; h>i ; i++)
        //cout << b[i][0].F.F << " " << b[i][0].F.S << " " << b[i][0].S.F << " " << b[i][0].S.S << "\n";
    for(int j = 1 ; w>j ; j++)
    {
        fc.clear();
        fcc.clear();
        for(int i = 0 ; h>i ; i++)
            fc.in(a[i][j]);
        for(int i = 0 ; h>i ; i++)
        {
            if(i==h-1&&j==w-1)
                continue;
            fc.erase(fc.find(a[i][j]));
            fcc.in(a[i][j]);
            auto it = fcc.begin();
            ll mn1 = *it;
            it=fcc.end();
            it--;
            ll mx1 = *it;
            ll mn2 = mnmx[j+1].F;
            ll mx2 = mnmx[j+1].S;
            if(!fc.empty())
            {
                it = fc.begin();
                mn2=min(mn2,*it);
                it = fc.end();
                it--;
                mx2=max(mx2,*it);
            }
            ll ans1 = 1e10;
            ll idx = -1;
            for(int p = i ; h>p ; p++)
            {
                ll mnn1 = mn1;
                ll mnn2 = mn2;
                ll mxx1 = mx1;
                ll mxx2 = mx2;
                mnn1 = min(mnn1 , b[p][j-1].F.F);
                mnn2 = min(mnn2 , b[p][j-1].S.F);
                mxx1 = max(mxx1 , b[p][j-1].F.S);
                mxx2 = max(mxx2 , b[p][j-1].S.S);
                //if(j==2)
                    //cout << mn1 << " " << mx1 << " " << b[p][j-1].F.F << " " << b[p][j-1].F.S << "\n";
                ll ans2 = max(mxx1-mnn1,mxx2-mnn2);
                if(ans2<=ans1)
                {
                    ans1=ans2;
                    idx=p;
                }
            }
            //cout << i << " " << j << " " << idx << " " << j-1 << "\n";
            ans[i][j]=ans1;
            mn1=min(mn1,b[idx][j-1].F.F);
            mx1=max(mx1,b[idx][j-1].F.S);
            mx2=b[idx][j-1].S.S;
            mn2=b[idx][j-1].S.F;
            if(!fc.empty())
            {
                it = fc.begin();
                mn2=min(mn2,*it);
                it = fc.end();
                it--;
                mx2=max(mx2,*it);
            }
            b[i][j].F.F=mn1;
            b[i][j].F.S=mx1;
            b[i][j].S.F=mn2;
            b[i][j].S.S=mx2;
        }
    }
    ans[h-1][w-1]=1e10;
    ll anss = 1e10;
   //cout << ans[1][2] << " ";
    for(int i = 0 ; h>i ; i++)
        for(int j = 0 ; w>j ; j++)
            anss=min(anss,ans[i][j]);
    for(int j = 0 ; w>j ; j++)
    {
        for(int i = 0 ; h/2>i ; i++)
        {
            ll qq = a[i][j];
            a[i][j]=a[h-i-1][j];
            a[h-i-1][j]=qq;
        }
    }
    fc.clear();
    fcc.clear();
    for(int i = 0 ; h>i ; i++)
        fc.in(a[i][0]);
    for(int i = 0 ; h>i ; i++)
    {
        fc.erase(fc.find(a[i][0]));
        fcc.in(a[i][0]);
        auto it = fcc.begin();
        ll mn = *it;
        it = fcc.end();
        it--;
        ll mx = *it;
        ans[i][0]=mx-mn;
        b[i][0].F.F=mn;
        b[i][0].F.S=mx;
        mn = mnmx[1].F;
        mx = mnmx[1].S;
        //cout << mn << " " << mx << "\n";
        b[i][0].S.F=1e10;
        b[i][0].S.S=0;
        if(fc.size())
        {
            it = fc.begin();
            b[i][0].S.F=*it;
            mn=min(mn,*it);
            it = fc.end();
            it--;
            b[i][0].S.S=*it;
            mx=max(mx,*it);
        }
        ans[i][0] = max(ans[i][0],mx-mn);
    }
    //for(int i = 0 ; h>i ; i++)
        //cout << b[i][0].F.F << " " << b[i][0].F.S << " " << b[i][0].S.F << " " << b[i][0].S.S << "\n";
    for(int j = 1 ; w>j ; j++)
    {
        fc.clear();
        fcc.clear();
        for(int i = 0 ; h>i ; i++)
            fc.in(a[i][j]);
        for(int i = 0 ; h>i ; i++)
        {
            if(i==h-1&&j==w-1)
                continue;
            fc.erase(fc.find(a[i][j]));
            fcc.in(a[i][j]);
            auto it = fcc.begin();
            ll mn1 = *it;
            it=fcc.end();
            it--;
            ll mx1 = *it;
            ll mn2 = mnmx[j+1].F;
            ll mx2 = mnmx[j+1].S;
            if(!fc.empty())
            {
                it = fc.begin();
                mn2=min(mn2,*it);
                it = fc.end();
                it--;
                mx2=max(mx2,*it);
            }
            ll ans1 = 1e10;
            ll idx = -1;
            ll mnnn1 =-1 , mxxx1 =-1 , mnnn2 =-1 , mxxx2 =-1;
            for(int p = i ; h>p ; p++)
            {
                ll mnn1 = mn1;
                ll mnn2 = mn2;
                ll mxx1 = mx1;
                ll mxx2 = mx2;
                mnn1 = min(mnn1 , b[p][j-1].F.F);
                mnn2 = min(mnn2 , b[p][j-1].S.F);
                mxx1 = max(mxx1 , b[p][j-1].F.S);
                mxx2 = max(mxx2 , b[p][j-1].S.S);
                //if(i==4&&j==1)
                    //cout << mn1 << " " << mx1 << " " << b[p][j-1].F.F << " " << b[p][j-1].F.S << "\n";
                ll ans2 = max(mxx1-mnn1,mxx2-mnn2);
                if(ans2<ans1)
                {
                    ans1=ans2;
                    idx=p;
                    mnnn1=mn1;
                    mnnn2=mn2;
                    mxxx1=mx1;
                    mxxx2=mx2;
                }
                else if(ans2==ans1&&mnnn1==mnn1&&mxxx1==mxx1&&mnnn2==mnn2&&mxxx2==mxx2)
                {
                    ans1=ans2;
                    idx=p;
                }
            }
            //if(i==4&&j==1)
                //cout << i << " " << j << " " << idx << " " << j-1 << "\n";
            ans[i][j]=ans1;
            mn1=min(mn1,b[idx][j-1].F.F);
            mx1=max(mx1,b[idx][j-1].F.S);
            mx2=b[idx][j-1].S.S;
            mn2=b[idx][j-1].S.F;
            if(!fc.empty())
            {
                it = fc.begin();
                mn2=min(mn2,*it);
                it = fc.end();
                it--;
                mx2=max(mx2,*it);
            }
            b[i][j].F.F=mn1;
            b[i][j].F.S=mx1;
            b[i][j].S.F=mn2;
            b[i][j].S.S=mx2;
        }
    }
    ans[h-1][w-1]=1e10;
    //cout << b[4][0].F.F << " " << b[4][0].F.S << " " << b[4][0].S.F << " " << b[4][0].S.S << "\n";
    //cout << ans[1][2] << " ";
    for(int i = 0 ; h>i ; i++)
        for(int j = 0 ; w>j ; j++)
            anss=min(anss,ans[i][j]);
    cout << anss;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40