Submission #931328

#	Time	Username	Problem	Language	Result	Execution time	Memory
931328		De3b0o	The Kingdom of JOIOI (JOI17_joioi)	C++14	15 / 100	113 ms	452 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;

ll h , w;
ll a[10][10];
ll b[10];

ll W(ll col , ll row , ll mn1 , ll mx1 , ll mn2 , ll mx2)
{
    if(col==w-1)
    {
        //cout << col << " " << row << " " << mn1 << " " << mx1 << " " << mn2 << " " << mx2 << " " << max(mx1-mn1,mx2-mn2) << "\n";
        return max(mx1-mn1,mx2-mn2);
    }
    multiset<ll> s1;
    multiset<ll> s2;
    for(int i = 0 ; h>i ; i++)
        s2.in(a[i][col+1]);
    auto it = s2.begin();
    ll mn = *it;
    it = s2.end();
    it--;
    ll mx = *it;
    ll ans = W(col+1,0,mn1,mx1,min(mn2,mn),max(mx2,mx));
    b[col]=0;
    for(int i = 0 ; row>i ; i++)
    {
        s1.in(a[i][col+1]);
        s2.erase(s2.find(a[i][col+1]));
        it = s1.begin();
        ll mnn1 = min(mn1,*it);
        it = s1.end();
        it--;
        ll mxx1 = max(mx1,*it);
        ll mnn2 = mn2;
        ll mxx2 = mx2;
        if(!s2.empty())
        {
            it = s2.begin();
            mnn2=min(mnn2,*it);
            it = s2.end();
            it--;
            mxx2=max(mxx2,*it);
        }
        ll ans1 = ans;
        ans=min(ans,W(col+1,i+1,mnn1,mxx1,mnn2,mxx2));
        if(ans!=ans1)
            b[col]=i+1;
    }
    return ans;
}

int main()
{
    d3
    cin >> h >> w;
    for(int i = 0 ; h>i ; i++)
        for(int j = 0 ; w>j ; j++)
            cin >> a[i][j];
    multiset<ll> s1;
    multiset<ll> s2;
    for(int i = 0 ; h>i ; i++)
        s2.in(a[i][0]);
    ll ans = 1e10;
    for(int i = 0 ; h>i ; i++)
    {
        s1.in(a[i][0]);
        s2.erase(s2.find(a[i][0]));
        auto it = s1.begin();
        ll mnn1 = *it;
        it = s1.end();
        it--;
        ll mxx1 = *it;
        ll mnn2 = 1e10;
        ll mxx2 = 0;
        if(!s2.empty())
        {
            it = s2.begin();
            mnn2=min(mnn2,*it);
            it = s2.end();
            it--;
            mxx2=max(mxx2,*it);
        }
        //cout << i+1 << " " << mnn1 << " " << mxx1 << " " << mnn2 << " " << mxx2 << '\n';
        ll ans1 = ans;
        ans=min(ans,W(0,i+1,mnn1,mxx1,mnn2,mxx2));
        if(ans1!=ans)
            b[0]=i+1;
    }
    //for(int i = 0 ; w>i ; i++)
        //cout << b[i] << " ";
    for(int j = 0 ; w>j ; j++)
    {
        for(int i = 0 ; h/2>i ; i++)
        {
            ll x = a[i][j];
            a[i][j]=a[h-i-1][j];
            a[h-i-1][j]=x;
        }
    }
    /*for(int i = 0 ; h>i ; i++)
        for(int j = 0 ; w>j ; j++)
            cout << a[i][j] << " ";*/
    s1.clear();
    s2.clear();
    for(int i = 0 ; h>i ; i++)
        s2.in(a[i][0]);
    for(int i = 0 ; h>i ; i++)
    {
        s1.in(a[i][0]);
        s2.erase(s2.find(a[i][0]));
        auto it = s1.begin();
        ll mnn1 = *it;
        it = s1.end();
        it--;
        ll mxx1 = *it;
        ll mnn2 = 1e10;
        ll mxx2 = 0;
        if(!s2.empty())
        {
            it = s2.begin();
            mnn2=min(mnn2,*it);
            it = s2.end();
            it--;
            mxx2=max(mxx2,*it);
        }
        //cout << i+1 << " " << mnn1 << " " << mxx1 << " " << mnn2 << " " << mxx2 << '\n';
        ll ans1 = ans;
        ans=min(ans,W(0,i+1,mnn1,mxx1,mnn2,mxx2));
        if(ans1!=ans)
            b[0]=i+1;
    }
    cans
}

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