oj.uz

Submission #931328

# Submission time Handle Problem Language Result Execution time Memory
931328 2024-02-21T15:29:24 Z De3b0o The Kingdom of JOIOI (JOI17_joioi) C++14
15 / 100
 113 ms 452 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 105 ms 348 KB Output is correct
4 Correct 53 ms 344 KB Output is correct
5 Correct 106 ms 344 KB Output is correct
6 Correct 23 ms 348 KB Output is correct
7 Correct 108 ms 348 KB Output is correct
8 Correct 111 ms 348 KB Output is correct
9 Correct 108 ms 436 KB Output is correct
10 Correct 112 ms 452 KB Output is correct
11 Correct 109 ms 436 KB Output is correct
12 Correct 107 ms 348 KB Output is correct
13 Correct 107 ms 348 KB Output is correct
14 Correct 113 ms 432 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 105 ms 348 KB Output is correct
4 Correct 53 ms 344 KB Output is correct
5 Correct 106 ms 344 KB Output is correct
6 Correct 23 ms 348 KB Output is correct
7 Correct 108 ms 348 KB Output is correct
8 Correct 111 ms 348 KB Output is correct
9 Correct 108 ms 436 KB Output is correct
10 Correct 112 ms 452 KB Output is correct
11 Correct 109 ms 436 KB Output is correct
12 Correct 107 ms 348 KB Output is correct
13 Correct 107 ms 348 KB Output is correct
14 Correct 113 ms 432 KB Output is correct
15 Correct 2 ms 344 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 105 ms 348 KB Output is correct
4 Correct 53 ms 344 KB Output is correct
5 Correct 106 ms 344 KB Output is correct
6 Correct 23 ms 348 KB Output is correct
7 Correct 108 ms 348 KB Output is correct
8 Correct 111 ms 348 KB Output is correct
9 Correct 108 ms 436 KB Output is correct
10 Correct 112 ms 452 KB Output is correct
11 Correct 109 ms 436 KB Output is correct
12 Correct 107 ms 348 KB Output is correct
13 Correct 107 ms 348 KB Output is correct
14 Correct 113 ms 432 KB Output is correct
15 Correct 2 ms 344 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -