oj.uz

Submission #82760

# Submission time Handle Problem Language Result Execution time Memory
82760 2018-11-01T15:09:30 Z Bodo171 The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 975 ms 20504 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
int a[nmax][nmax];
int mn,mx,ans,n,m,i,j;
int st,dr,l,r;
bool cresc,desc;
bool check(int val)
{
    st=0,dr=m;
    cresc=1,desc=1;
    for(i=1;i<=n&&(cresc||desc);i++)
    {
        r=1;l=m;
        while(a[i][r]-mn<=val&&r<=m)
            r++;
        r--;
        while(mx-a[i][l]<=val&&l>0)
            l--;
        st=max(st,l);dr=min(r,dr);
        if(st>r)
            cresc=0;
        if(dr<l)
            desc=0;
    }
    return (cresc||desc);
}
int solve()
{
    int ret=(1<<30)-1;
    for(int p=29;p>=0;p--)
        if(check(ret-(1<<p)))
           ret-=(1<<p);
    return ret;
}
int main()
{
   // freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;mn=(1<<30);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        cin>>a[i][j];
        mn=min(a[i][j],mn);
        mx=max(a[i][j],mx);
    }
    ans=mx-mn;
    ans=min(solve(),ans);
    for(i=1;i<=n;i++)
        for(j=1;j<=m/2;j++)
            swap(a[i][j],a[i][m-j+1]);
    ans=min(solve(),ans);
    cout<<ans;
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 612 KB Output is correct
11 Correct 2 ms 612 KB Output is correct
12 Correct 2 ms 628 KB Output is correct
13 Correct 2 ms 704 KB Output is correct
14 Correct 2 ms 704 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 612 KB Output is correct
11 Correct 2 ms 612 KB Output is correct
12 Correct 2 ms 628 KB Output is correct
13 Correct 2 ms 704 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 3 ms 704 KB Output is correct
16 Correct 12 ms 1688 KB Output is correct
17 Correct 13 ms 1892 KB Output is correct
18 Correct 12 ms 2164 KB Output is correct
19 Correct 13 ms 2432 KB Output is correct
20 Correct 12 ms 2576 KB Output is correct
21 Correct 13 ms 3152 KB Output is correct
22 Correct 13 ms 3460 KB Output is correct
23 Correct 13 ms 3844 KB Output is correct
24 Correct 11 ms 4108 KB Output is correct
25 Correct 13 ms 4576 KB Output is correct
26 Correct 13 ms 5052 KB Output is correct
27 Correct 14 ms 5492 KB Output is correct
28 Correct 15 ms 5640 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 612 KB Output is correct
11 Correct 2 ms 612 KB Output is correct
12 Correct 2 ms 628 KB Output is correct
13 Correct 2 ms 704 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 3 ms 704 KB Output is correct
16 Correct 12 ms 1688 KB Output is correct
17 Correct 13 ms 1892 KB Output is correct
18 Correct 12 ms 2164 KB Output is correct
19 Correct 13 ms 2432 KB Output is correct
20 Correct 12 ms 2576 KB Output is correct
21 Correct 13 ms 3152 KB Output is correct
22 Correct 13 ms 3460 KB Output is correct
23 Correct 13 ms 3844 KB Output is correct
24 Correct 11 ms 4108 KB Output is correct
25 Correct 13 ms 4576 KB Output is correct
26 Correct 13 ms 5052 KB Output is correct
27 Correct 14 ms 5492 KB Output is correct
28 Correct 15 ms 5640 KB Output is correct
29 Correct 874 ms 19624 KB Output is correct
30 Correct 925 ms 20404 KB Output is correct
31 Correct 937 ms 20404 KB Output is correct
32 Correct 975 ms 20412 KB Output is correct
33 Correct 817 ms 20412 KB Output is correct
34 Correct 919 ms 20492 KB Output is correct
35 Correct 975 ms 20504 KB Output is correct
36 Correct 821 ms 20504 KB Output is correct
37 Correct 939 ms 20504 KB Output is correct