Submission #691938

#	Time	Username	Problem	Language	Result	Execution time	Memory
691938		Paul_Liao_1457	The Kingdom of JOIOI (JOI17_joioi)	C++17	15 / 100	4085 ms	596 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 int ll
#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[2005][2005],pre[2][2005][2005],suf[2][2005][2005];
vector<int> num[15];

int h,w,ans=INF;

void dfs(int i,int j,int max1,int min1,int max2,int min2){
    if(i==h+1){
        if(j==0) return;
        //cout<<max1<<" "<<min1<<" "<<max2<<" "<<min2<<endl;
        ans=min(ans,max(max1-min1,max2-min2)); return;
    }
    FOR(x,j,w+1){
        dfs(i+1,x,max(max1,pre[1][i][x]),min(min1,pre[0][i][x]),max(max2,suf[1][i][x+1]),min(min2,suf[0][i][x+1]));
    }
}

void dfs2(int i,int j,int max1,int min1,int max2,int min2){
    //cout<<"i="<<i<<" j="<<j<<endl;
    //cout<<max1<<" "<<min1<<" "<<max2<<" "<<min2<<endl;
    if(i==h+1){
        if(j==w) return;
        ans=min(ans,max(max1-min1,max2-min2)); return;
    }
    REP(x,j,0){
        dfs2(i+1,x,max(max1,pre[1][i][x]),min(min1,pre[0][i][x]),max(max2,suf[1][i][x+1]),min(min2,suf[0][i][x+1]));
    }
}

signed main(){
    AC;
    cin>>h>>w;
    FOR(i,1,h+1)FOR(j,1,w+1) cin>>a[i][j];
    FOR(i,1,h+1){
        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[i][j]);
            pre[1][i][j]=max(pre[1][i][j-1],a[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[i][j]);
            suf[1][i][j]=max(suf[1][i][j+1],a[i][j]);
        }
    }
    dfs(1,0,0,INF,0,INF);
    dfs2(1,w,0,INF,0,INF);
    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: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_in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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