oj.uz

Submission #230704

# Submission time Handle Problem Language Result Execution time Memory
230704 2020-05-11T08:59:38 Z mohamedsobhi777 The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 16 ms 16256 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16256 KB Output is correct
2 Incorrect 16 ms 16256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16256 KB Output is correct
2 Incorrect 16 ms 16256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16256 KB Output is correct
2 Incorrect 16 ms 16256 KB Output isn't correct
3 Halted 0 ms 0 KB -