Submission #199259

#	Time	Username	Problem	Language	Result	Execution time	Memory
199259		Mercenary	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	831 ms	55032 KiB

joioi

#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 2e3 + 5;
int n , m , a[maxn][maxn] , Mi = 1e9 , Ma = 0;
int res = 0;
bool check(int val){
    int L = 1 ,  R = m;
    bool ok = 1  , ok1 = 1;
    for(int i = 1 ; i <= n ; ++i){
        int l = m , r = 1;
        int Mi = 1e9 , Ma = 0;
        for( ; l >= 1 ; --l){
            Ma = max(Ma , a[i][l]);
            if(Ma - ::Mi > val)break;
        }
        for( ; r <= m ; ++r){
            Mi = min(Mi , a[i][r]);
            if(::Ma - Mi > val)break;
        }
        --r;++l;
        R = min(R , r);
        if(R < l - 1)ok = 0;
        L = max(L , l);
        if(r + 1 < L)ok1 = 0;
//        cout << l << " " << r << endl;
    }
//    cout << endl;
    if(ok || ok1)return 1;
    ok = 1 , ok1 = 1;
    L = 1;R = m;
    for(int i = 1 ; i <= n ; ++i){
        int l = m , r = 1;
        int Mi = 1e9 , Ma = 0;
        for( ; l >= 1 ; --l){
            Mi = min(Mi , a[i][l]);
            if(::Ma - Mi > val)break;
        }
        for( ; r <= m ; ++r){
            Ma = max(Ma , a[i][r]);
            if(Ma - ::Mi > val)break;
        }
        --r;++l;
        R = min(R , r);
        if(R < l - 1)ok = 0;
        L = max(L , l);
        if(r + 1 < L)ok1 = 0;
//        cout << l << " " << r << endl;
    }
    if(ok || ok1)return 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j){
        cin >> a[i][j];
        Mi = min(Mi,a[i][j]);Ma = max(Ma,a[i][j]);
    }
//    return cout << check(1) , 0;
    int l = 0, h = 1e9;
    while(l <= h){
        int mid = l + h >> 1;
        if(check(mid))h = mid - 1;
        else l = mid + 1;
    }
    cout << min(l , Ma - Mi);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:77:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + h >> 1;
                   ~~^~~
joioi.cpp:66:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:67:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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