Submission #233451

#	Time	Username	Problem	Language	Result	Execution time	Memory
233451		nicolaalexandra	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3022 ms	35832 KiB

joioi

#include <bits/stdc++.h>
#define DIM 2010
#define DIMBUFF 30000000
#define INF 2000000000
using namespace std;
int a[DIM][DIM],b[DIM][DIM],viz[DIM][DIM];
struct idk{
    int val,l,c;
} v[DIM*DIM];
pair<int,int> c[DIM*DIM];
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
int n,m,i,j,sol,mini,maxi,k,pos;
char buff[DIMBUFF];

int verif (int val){

    int last = 0;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            if (a[i][j] < maxi - val)
                last = max(last,j);
        }

        for (j=1;j<=m;j++)
            if (a[i][j] > mini + val && j <= last)
                return 0;
    }

    return 1;
}

void solve (){

    int st = 0, dr = maxi - mini, val = INF;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif (mid)){
            val = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    sol = min (sol,val);

}

inline int cmp (idk a, idk b){
    return a.val < b.val;
}


void roteste_linii(){
    for (i=1;i<=n/2;i++)
        for (j=1;j<=m;j++)
            swap (a[i][j],a[n-i+1][j]);
}
void roteste_coloane(){
    for (i=1;i<=n;i++)
        for (j=1;j<=m/2;j++)
            swap (a[i][j],a[i][m-j+1]);
}

int get_nr(){
    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        ++pos;
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr*10 + buff[pos] - '0';
        ++pos;
    }
    return nr;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;

    mini = INF;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j){
            cin>>a[i][j];
            mini = min (mini,a[i][j]);
            maxi = max (maxi,a[i][j]);
           // v[++k] = {a[i][j],i,j};
        }

    //sort (v+1,v+k+1,cmp);

    sol = INF;
    solve();

    roteste_linii();
    solve();

    roteste_coloane();
    solve();

    roteste_linii();
    solve();

    cout<<sol;

    return 0;
}

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