Submission #225368

#	Time	Username	Problem	Language	Result	Execution time	Memory
225368		MKopchev	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1069 ms	55416 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e3+42;

int n,m;

int inp[nmax][nmax];

int mini,maxi;

int output;

bool can(int cur)
{
    int j_line=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(inp[i][j]-mini>cur)j_line=max(j_line,j);

        for(int j=1;j<=j_line;j++)
            if(maxi-inp[i][j]>cur)return 0;

        for(int j=j_line+1;j<=m;j++)
            if(inp[i][j]-mini>cur)return 0;
    }
    return 1;
}
void solve()
{
    int ok=output,not_ok=-1;
    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;
        if(can(av))ok=av;
        else not_ok=av;
    }
    output=ok;
}

void rotate_1()
{
    for(int i=1;i<n+1-i;i++)
        for(int j=1;j<=m;j++)
            swap(inp[i][j],inp[n+1-i][j]);
}

void rotate_2()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<m+1-j;j++)
            swap(inp[i][j],inp[i][m+1-j]);
}

int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%i",&inp[i][j]);

    mini=inp[1][1];
    maxi=inp[1][1];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            mini=min(mini,inp[i][j]);
            maxi=max(maxi,inp[i][j]);
        }

    output=maxi-mini;

    solve();

    rotate_1();
    solve();

    rotate_2();
    solve();

    rotate_1();
    solve();

    printf("%i\n",output);
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
joioi.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&inp[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~

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