Submission #224704

#	Time	Username	Problem	Language	Result	Execution time	Memory
224704		Ruxandra985	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	7 ms	640 KiB

joioi

#include <bits/stdc++.h>
#define DIMN 2010
using namespace std;

int mini , maxi , n , m , sol;
int a[DIMN][DIMN] , where[DIMN][DIMN] , h[DIMN];
priority_queue <pair <int , pair <int,int> > > up , down;


void solve(){
    int i , j , maxis , minis , maxij , minij , val , ic , jc;

    /// jos includ mini, sus includ maxi

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++)
            where[i][j] = 0;
    }

    for (j = 1 ; j <= m ; j++){

        for (i = 1 ; i <= n ; i++){
            if (a[i][j] == mini)
                break;
        }

        h[j] = max(n - i + 1 , h[j - 1]); /// fie iau exact cat trb fie mai mult


        for (i = 1 ; i <= h[j] ; i++)
            where[n - i + 1][j] = 1; /// apartine tarii de jos

    }

    minij = minis = 2000000000;
    maxij = maxis = -2000000000;

    /// e clar ca toate mini urile sunt jos

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            if (where[i][j] == 0){
                minis = min (minis , a[i][j]);
                maxis = max (maxis , a[i][j]);
            }
            else {
                minij = min (minij , a[i][j]);
                maxij = max (maxij , a[i][j]);
            }
        }
    }

    /// daca exista vreun maxi jos, nu e ok

    if (maxij == maxi)
        return;

    /// altfel, toate mini urile sunt jos, toate maxi urile sunt sus

    while (!down.empty())
        down.pop();
    while (!up.empty())
        up.pop();

    for (j = 1 ; j <= m ; j++){
        if (j == m || h[j] < h[j + 1])
            down.push( make_pair( -a[n - h[j]][j] , make_pair(n - h[j] , j)) );
    }

    /// in down pui candidatii


    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            if (where[i][j] == 0){
                up.push( make_pair( -a[i][j] , make_pair(i , j)) );
            }
        }
    }

    while (!down.empty()){

        val = -down.top().first;
        ic = down.top().second.first;
        jc = down.top().second.second;

        down.pop();

        /// val = cea mai mica val cu care pot sa extind

        maxij = max(maxij , val);

        where[ic][jc] = 1;

        h[jc]++;

        if (h[jc - 1] + 1 == h[jc] && jc - 1 != 0)
            down.push( make_pair( -a[n - h[jc - 1]][jc - 1] , make_pair(n - h[jc - 1] , jc - 1)) );

        if (jc == m || h[jc] != h[jc + 1])
            down.push( make_pair( -a[n - h[jc]][jc] , make_pair(n - h[jc] , jc)) );

        val = -up.top().first;
        minis = val;
        ic = up.top().second.first;
        jc = up.top().second.second;

        while (where[ic][jc]){
            up.pop();
            if (up.empty())
                break;
            val = -up.top().first;
            ic = up.top().second.first;
            jc = up.top().second.second;
            minis = val;
        }
        if (!up.empty())
            sol = min(sol , max(maxis - minis , maxij - minij));
        else break;
    }


}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , j , st , dr;
    fscanf (fin,"%d%d",&n,&m);

    mini = 2000000000;
    maxi = -2000000000;

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            fscanf (fin,"%d",&a[i][j]);
            mini = min(mini , a[i][j]);
            maxi = max(maxi , a[i][j]);
        }
    }

    sol = maxi - mini;

    solve();

    for (i = 1 ; i <= n ; i++){
        st = 1;
        dr = m;
        while (st < dr){
            swap(a[i][st] , a[i][dr]);
            st++;
            dr--;
        }
    }

    solve();

    for (j = 1 ; j <= m ; j++){
        st = 1;
        dr = n;
        while (st < dr){
            swap(a[st][j] , a[dr][j]);
            st++;
            dr--;
        }
    }

    solve();

    for (i = 1 ; i <= n ; i++){
        st = 1;
        dr = m;
        while (st < dr){
            swap(a[i][st] , a[i][dr]);
            st++;
            dr--;
        }
    }

    solve();

    fprintf (fout,"%d",sol);

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:130:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
joioi.cpp:137:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d",&a[i][j]);
             ~~~~~~~^~~~~~~~~~~~~~~~~~~

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