Submission #54498

#	Time	Username	Problem	Language	Result	Execution time	Memory
54498		bogdan10bos	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	1165 ms	263168 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

int N, M, ans;
int mn, mx;
int pfxmn[2005], sfxmx[2005];
int aux[2005][2005];
int a[2005][2005];
int dp[2005][2005];

void solve()
{
    for(int i = 1; i <= N; i++)
    {
        pfxmn[0] = 1 << 30;
        for(int j = 1; j <= M; j++) pfxmn[j] = min(pfxmn[j - 1], a[i][j]);
        sfxmx[M + 1] = -1;
        for(int j = M; j >= 1; j--) sfxmx[j] = max(sfxmx[j + 1], a[i][j]);

        for(int j = M; j >= 0; j--)
        {
            int cost = max(mx - pfxmn[j], sfxmx[j + 1] - mn);
            dp[i][j] = max(dp[i - 1][j], cost);
            if(j < M)   dp[i][j] = min(dp[i][j], dp[i][j + 1]);
        }
    }
    ans = min(ans, dp[N][0]);
}

void rotate90()
{
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            aux[i][j] = a[i][j];
            a[i][j] = 0;
        }
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            a[j][N - i + 1] = aux[i][j];
    swap(N, M);
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    mn = 1 << 30, mx = -1;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            scanf("%d", &a[i][j]);
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }

    ans = mx - mn;

    solve();
    rotate90();
    solve();
    rotate90();
    solve();
    rotate90();
    solve();

    printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

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