Submission #191339

#	Time	Username	Problem	Language	Result	Execution time	Memory
191339		Akashi	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4021 ms	54988 KiB

joioi

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

int n, m;
int Min, Max;
int a[2005][2005];

inline bool check(int dif, bool dir1, bool dir2){
    int i, j = 1;

    int adc = 1, adl = 1, Last = n;
    if(dir1 == 1) adc = -1, j = m;
    if(dir2 == 1) adl = -1, Last = 1;

    int mx = 0, mn = 1e9;
    while(j <= m && j >= 1){
        i = 1;
        if(dir2) i = n;

        while(Min + dif >= a[i][j] && (Last - i) * adl >= 0) i += adl;

        Last = i - adl;
        while(i <= n && i >= 1){
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
            i += adl;
        }

        j += adc;
    }

    if(mx - mn <= dif) return 1;
    return 0;
}

inline int solve(){
    int st = 0, dr = Max - Min;
    while(st <= dr){
        int mij = (st + dr) / 2;

        bool ok = false;
        for(int dir1 = 0; dir1 < 2 ; ++dir1)
            for(int dir2 = 0; dir2 < 2 ; ++dir2)
                ok |= check(mij, dir1, dir2);

        if(ok) dr = mij - 1;
        else st = mij + 1;
    }

    return st;
}

int main()
{
    scanf("%d%d", &n, &m);

    Min = 1e9; Max = 0;
    for(int i = 1; i <= n ; ++i){
        for(int j = 1; j <= m ; ++j){
            scanf("%d", &a[i][j]);
            Min = min(Min, a[i][j]);
            Max = max(Max, a[i][j]);
        }
    }

    int Sol = solve();
    printf("%d", Sol);

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

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