Submission #230704

#	Time	Username	Problem	Language	Result	Execution time	Memory
230704		mohamedsobhi777	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	16 ms	16256 KiB

joioi

#include<bits/stdc++.h>

using namespace std ; 

const int N = 2000 + 10 ; 

int n , m ;
int a[N][N] , b[N][N] ; 

int mxr[N] , mnr[N] ; 

int calc(pair<int ,int > pr) {
        return pr.first - pr.second ; 
}

pair<int , int> rett(pair<int , int> pr , pair<int , int> ch){
        pr.first = max(pr.first , ch.first) ; 
        pr.second = min(pr.second , ch.second) ; 
        return pr ; 
}

int solve(  ){
        int ret = 1e9 ; 
        for(int i = 0 ;i < n ; i++){
                mnr[i] = 1e9 ; 
                mxr[i] = 0 ; 
                for(int j = 0 ; j < m ;j++){
                        mxr[i] = max(mxr[i] , a[i][j]) ; 
                        mnr[i] = min(mnr[i] , a[i][j]) ; 
                }
        }

        pair<int , int > pr1 = {0 , 1e9} ; 
        for(int i = 0 ; i< n ;i++){
                pair<int , int> pr2 = {0 , 1e9} ; 
                for(int j = i+1 ;j < n ;j++){
                        pr2 = rett(pr2 , {mxr[j] , mnr[j]}) ; 
                }
                vector<int> mxp(m+1 , 0 )  , mxs(m+1 , 0) ; 
                vector<int> mnp(m+1 , 1e9) , mns(m+1 , 1e9) ; 

                mxp[0] = mnp[0] = a[i][0] ; 
                for(int j = 1 ;j < m ;j++){
                        mxp[j] = max(mxp[j-1] , a[i][j]) ; 
                        mnp[j] = min(mnp[j] , a[i][j]) ; 
                }
                mxs[m-1] = mns[m-1] = a[i][m-1] ; 
                for(int j = m-2 ;j>=0 ;j --){
                        mxs[j] = max(mxs[j+1] , a[i][j]) ; 
                        mns[j] = min(mns[j+1] , a[i][j]) ; 
                }
                mns[m] = -1e9 ; 
                if(i)
                        ret = min(ret , calc(pr1) + calc(rett(pr2 , {mxr[i] , mnr[i]} )) ) ; 
                for(int j = 0 ;j < m ;j++){
                        ret = min(ret , calc( rett(pr1 , {mxp[j] , mnp[j]}) ) + calc(rett( pr2 , {mxs[j+1] , mns[j+1]} ) ) ) ; 
                }

                pr1 = rett(pr1 , { mxr[i] , mnr[i] }) ; 
        }

        return ret ; 
}

int main(){
        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ; 

        cin>>n>>m ; 

        for(int i = 0 ;i < n ;i++){
                for(int j = 0 ;j < m; j++){
                        cin>>a[i][j]; 
                        b[j][i] = a[i][j] ; 
                }
        }
        int ans = solve() ; 
        swap(n ,m ) ; 
        ans = min(ans , solve()) ; 

        for(int i = 0 ; i < N ;i++){
                for(int j = 0 ;j < N ; j++){
                        a[i][j] = b[i][j] ; 
                }
        }
        cout<< ans ; 
        return 0 ; 
}

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