Submission #906279

#	Time	Username	Problem	Language	Result	Execution time	Memory
906279		Maite_Morale	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	2953 ms	262144 KiB

joioi

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 3005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
    
ll tmn[5][MAX][MAX],tmx[5][MAX][MAX],n,a[MAX][MAX],m;
map<ll,ll> mp;
vll v;
ll OK(ll x,ll z){
    //cout<<x<<":  ";
    ll r=oo,mx=0,c=0;
    for(int i=1;i<=n;i++){
        while(c+1<=m && tmn[1][i][c+1]<x)c++;
        mx=max(mx,tmx[0][i][c]);
    }r=min(r,mx);
    //cout<<mx<<"  ";
    mx=0;c=0;
    for(int i=n;i>0;i--){
        while(c+1<=m && tmn[1][i][c+1]<x)c++;
        mx=max(mx,tmx[0][i][c]);
    }r=min(r,mx);
    //cout<<mx<<" ";
    mx=0;c=m+1;
    for(int i=1;i<=n;i++){
        while(c-1>=0 && tmn[0][i][c-1]<x)c--;
        mx=max(mx,tmx[1][i][c]);
    }r=min(r,mx);
    //cout<<mx<<" ";
    mx=0;c=m+1;
    for(int i=n;i>0;i--){
        while(c-1>=0 && tmn[0][i][c-1]<x)c--;
        mx=max(mx,tmx[1][i][c]);
    }r=min(r,mx);
    //cout<<mx<<"\n";
    if(z==1)return max(abs(r-v[0]),abs(v.back()-x));
    if(abs(r-v[0])>=abs(v.back()-x))return 0;
return 1;
}
int main(){
    fast_in
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(mp[a[i][j]]==0){
                mp[a[i][j]]=1;
                v.push_back(a[i][j]);
            }
        }
        tmx[0][i][0]=tmx[1][i][m+1]=0;
        tmn[0][i][0]=tmn[1][i][m+1]=oo;
        for(int j=1;j<=m;j++){
            tmx[0][i][j]=max(tmx[0][i][j-1],a[i][j]);
            tmn[0][i][j]=min(tmn[0][i][j-1],a[i][j]);
            
        }
        for(int j=m;j>0;j--){
            tmx[1][i][j]=max(tmx[1][i][j+1],a[i][j]);
            tmn[1][i][j]=min(tmn[1][i][j+1],a[i][j]);
            //cout<<tmn[1][i][j]<<" ";
        }//cout<<"\n";
    }sort(v.begin(),v.end());
    if(v.size()==1){cout<<0;return 0;}
    ll p=1,f=v.size();//cout<<f<<" ";
    while(abs(p-f)!=1){
        ll md=(p+f)/2;//cout<<md<<":";
        if(OK(v[md],0)==1)p=md;
        else            f=md;
    }
    cout<<min(OK(v[p],1),OK(v[f],1));
return 0;
}

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