Submission #692370

#	Time	Username	Problem	Language	Result	Execution time	Memory
692370		Paul_Liao_1457	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2982 ms	213928 KiB

joioi

//記得跳題
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
 
#define ll long long
#define LL __int128_t
#define DB double
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define INF (ll)(2e9)
#define MOD (ll)(1e9+7)
#define F first
#define S second
#define endl "\n"
#define AC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
 
struct func{
    bool operator()(const int &x, const int &y) const{
        return x<y;
    }
};
 
template<class T> using PQ=priority_queue<T,vector<T>,func>;
 
void file(){
    freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
    freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
}

int a[9][2005][2005],ih,iw,pre[2][2005][2005],suf[2][2005][2005];

int h,w;

void turn(int t){
    FOR(i,1,w+1){
        FOR(j,1,h+1){
            a[t][i][j]=a[t-1][j][w-i+1];
        }
    }
    swap(h,w);
}

void flap(int t){
    FOR(i,1,h+1){
        FOR(j,1,w+1){
            a[t][i][j]=a[t-1][h-i+1][w-j+1];
        }
    }
}

int now=0;
int minn=INF;

bool check(int k){
    //cout<<"k="<<k<<endl;
    h=ih; w=iw;
    now=0;
    FOR(i,1,8){
        bool ok=1;
        if(now==4) now++;
        FOR(i,1,h+1){
            pre[1][i][0]=0;
            suf[1][i][w+1]=0;
            pre[0][i][0]=INF;
            suf[0][i][w+1]=INF;
            FOR(j,1,w+1){
                pre[0][i][j]=min(pre[0][i][j-1],a[now][i][j]);
                pre[1][i][j]=max(pre[1][i][j-1],a[now][i][j]);
                //cout<<"pre["<<i<<"]["<<j<<"]="<<pre[1][i][j]<<endl;
            }
            REP(j,w,1){
                suf[0][i][j]=min(suf[0][i][j+1],a[now][i][j]);
                suf[1][i][j]=max(suf[1][i][j+1],a[now][i][j]);
                //cout<<"suf["<<i<<"]["<<j<<"]="<<suf[1][i][j]<<endl;
            }
        }
        int tmp=w,mi=INF,mx=0,lm=INF;
        FOR(x,1,h+1){
            while(tmp>0&&pre[1][x][tmp]>minn+k){
                tmp--;
            }
            lm=min(lm,pre[0][x][tmp]);
            mi=min(mi,suf[0][x][tmp+1]);
            mx=max(mx,suf[1][x][tmp+1]);
            //cout<<"mx="<<mx<<" mi="<<mi<<" lm="<<lm<<" tmp="<<tmp<<endl;
            if(mx-mi>k){
                ok=0; break;
            }
        }
        if(lm!=minn){
            ok=0;
        }
        if(ok){
            return 1;
        }
        swap(h,w); now++;
    }
    return 0;
}

signed main(){
    AC;
    cin>>h>>w; ih=h; iw=w;
    FOR(i,1,h+1)FOR(j,1,w+1){
        cin>>a[0][i][j]; minn=min(minn,a[0][i][j]);
    }
    
    int cur=0;
    FOR(i,1,8){
        cur++;
        if(i==4){
            cur++;
            flap(cur);
        }
        turn(cur);
    }
    
    int l=0,r=1e9+1,ans=INF;
    
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)){
            r=mid; ans=min(ans,mid);
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

 
/*
 4 5
 1 2 4 4
 1 3 2 1
 4 3 1 2
 4 1 6 1
 2 4 2 5
 
 */

Compilation message (stderr)

joioi.cpp: In function 'void file()':
joioi.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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