Submission #172480

#	Time	Username	Problem	Language	Result	Execution time	Memory
172480		mhy908	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1095 ms	55160 KiB

joioi

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int h, w;
int arr[2010][2010];
int minnum=inf;
int maxnum;

bool ch(int val){
    int st=0, dr=w;
    int cresc=1, desc=1;
    for(int i=1; i<=h&&(cresc||desc); i++){
        int r=1, l=w;
        while(arr[i][r]-minnum<=val&&r<=w)r++;
        r--;
        while(maxnum-arr[i][l]<=val&&l>0)l--;
        st=max(st, l);
        dr=min(r, dr);
        if(st>r)cresc=0;
        if(dr<l)desc=0;
    }
    return (cresc||desc);
}
int f(int st, int fin){
    if(st==fin)return st;
    int mid=(st+fin)/2;
    if(ch(mid))return f(st, mid);
    return f(mid+1, fin);
}
int main()
{
    scanf("%d %d", &h, &w);
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            scanf("%d", &arr[i][j]);
            minnum=min(minnum, arr[i][j]);
            maxnum=max(maxnum, arr[i][j]);
        }
    }
    int ans=f(0, 1000000000);
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w/2; j++){
            swap(arr[i][j], arr[i][w-j+1]);
        }
    }
    ans=min(ans, f(0, 1000000000));
    printf("%d", ans);
}

Compilation message (stderr)

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

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