Submission #83683

#	Time	Username	Problem	Language	Result	Execution time	Memory
83683		Vasiljko	The Kingdom of JOIOI (JOI17_joioi)	C++14	15 / 100	4035 ms	780 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;
const int N = 1e3+5;
const ll INF = 1e9+7;

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

void rec(int row,int col,int d){
    if(row==n+1){
        ll mx1=-INF,mx2=-INF;
        ll mn1=INF,mn2=INF;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=b[i];j++){
                mx1=max(mx1,a[i][j]);
                mn1=min(mn1,a[i][j]);
            }
            for(int j=b[i]+1;j<=m;j++){
                mx2=max(mx2,a[i][j]);
                mn2=min(mn2,a[i][j]);
            }
        }
        if(mx1==INF)mx1=0,mn1=0;
        if(mx2==INF)mx2=0,mn2=0;

        ll sol=max(mx1-mn1,mx2-mn2);
        ans=min(ans,sol);

        return;
    }
    b[row]=col;
    if(d==1)for(int i=col;i<=m;i++)rec(row+1,i,d);
    else for(int i=col;i>=0;i--)rec(row+1,i,d);
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];

    ans=10LL*INF;
    for(int i=0;i<=m;i++)rec(1,i,1);
    for(int i=0;i<=m;i++)rec(1,i,-1);
    cout<<ans;

    return 0;
}

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