oj.uz

Submission #83683

# Submission time Handle Problem Language Result Execution time Memory
83683 2018-11-09T19:02:50 Z Vasiljko The Kingdom of JOIOI (JOI17_joioi) C++14
15 / 100
 4000 ms 780 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 107 ms 500 KB Output is correct
4 Correct 53 ms 500 KB Output is correct
5 Correct 109 ms 500 KB Output is correct
6 Correct 23 ms 500 KB Output is correct
7 Correct 116 ms 560 KB Output is correct
8 Correct 110 ms 560 KB Output is correct
9 Correct 110 ms 624 KB Output is correct
10 Correct 107 ms 636 KB Output is correct
11 Correct 107 ms 636 KB Output is correct
12 Correct 107 ms 700 KB Output is correct
13 Correct 110 ms 776 KB Output is correct
14 Correct 109 ms 780 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 107 ms 500 KB Output is correct
4 Correct 53 ms 500 KB Output is correct
5 Correct 109 ms 500 KB Output is correct
6 Correct 23 ms 500 KB Output is correct
7 Correct 116 ms 560 KB Output is correct
8 Correct 110 ms 560 KB Output is correct
9 Correct 110 ms 624 KB Output is correct
10 Correct 107 ms 636 KB Output is correct
11 Correct 107 ms 636 KB Output is correct
12 Correct 107 ms 700 KB Output is correct
13 Correct 110 ms 776 KB Output is correct
14 Correct 109 ms 780 KB Output is correct
15 Execution timed out 4035 ms 780 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 107 ms 500 KB Output is correct
4 Correct 53 ms 500 KB Output is correct
5 Correct 109 ms 500 KB Output is correct
6 Correct 23 ms 500 KB Output is correct
7 Correct 116 ms 560 KB Output is correct
8 Correct 110 ms 560 KB Output is correct
9 Correct 110 ms 624 KB Output is correct
10 Correct 107 ms 636 KB Output is correct
11 Correct 107 ms 636 KB Output is correct
12 Correct 107 ms 700 KB Output is correct
13 Correct 110 ms 776 KB Output is correct
14 Correct 109 ms 780 KB Output is correct
15 Execution timed out 4035 ms 780 KB Time limit exceeded
16 Halted 0 ms 0 KB -