Submission #332083

#	Time	Username	Problem	Language	Result	Execution time	Memory
332083		maozkurt	The Kingdom of JOIOI (JOI17_joioi)	C++17	15 / 100	4075 ms	620 KiB

joioi

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn = 2005;

ll arr[maxn][maxn];

bool boya[maxn][maxn];
const ll inf = 1e9;

int h,w;
ll ans = inf;

ll calc(){
    ll joimin=inf,joimax = 0,ioimin=inf,ioimax=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(boya[i][j]){
                ioimax = max(ioimax,arr[i][j]);
                ioimin = min(ioimin,arr[i][j]);
            }
            else{
                joimax = max(joimax,arr[i][j]);
                joimin = min(joimin,arr[i][j]);
            }   
        }   
    }
    if(ioimin == inf || joimin == inf) return inf;
    return max(ioimax - ioimin, joimax - joimin);
}


void f(int derin, int kac){
    if(derin < 0) return;
    for(int i=0;i<w;i++) boya[derin][i] = false;
    for(int i=0;i<kac;i++){
        boya[derin][i] = true;
        ans = min(ans, calc());
        f(derin-1,i+1);
    }
    for(int i=0;i<w;i++) boya[derin][i] = false;
}


ll temprot[maxn][maxn];

void rot(){
   for(int i=0;i<w;i++){
        for(int j=0;j<h;j++){
            temprot[i][j] = arr[h-j-1][i];
        }
   }
   for(int i=0;i<w;i++){
       for(int j=0;j<h;j++){
            arr[i][j] = temprot[i][j];
       }
   }
   swap(h,w);
}
int main(){
    
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
    cin>>h>>w;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<4;i++){ 
        f(h-1,w);
        /*
        for(int k=0;k<h;k++){
            for(int l=0;l<w;l++)
                cout<<arr[k][l]<<sp;
            cout<<endl;
        } 
        cout<<endl;
        */
        rot();
    }
    cout << ans << endl;
    
     

}

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