oj.uz

Submission #50007

# Submission time Handle Problem Language Result Execution time Memory
50007 2018-06-06T08:08:32 Z Costin Andrei Oncescu(#1280, SpaimaCarpatilor) The Kingdom of JOIOI (JOI17_joioi) C++11
0 / 100
 3 ms 812 KB 
#include<bits/stdc++.h>

using namespace std;

int mi, ma, N, M, a[2009][2009];
bool dp[2009][2009], ok[2009][2009];
pair < int, int > pf[2009], sf[2009];

pair < int, int > combine (pair < int, int > a, pair < int, int > b)
{
    return {min (a.first, b.first), max (a.second, b.second)};
}

bool check (int maxD)
{
    int lft[2], rgt[2];
    lft[0] = mi, rgt[0] = mi + maxD;
    lft[1] = ma - maxD, rgt[1] = ma;
    for (int up = 0; up < 2; up ++)
    {
        for (int j=1; j<=M; j++)
        {
            pf[0] = {ma, mi}, sf[N + 1] = {ma, mi};
            for (int i=1; i<=N; i++)
                pf[i] = combine (pf[i - 1], {a[i][j], a[i][j]});
            for (int i=N; i>=1; i--)
                sf[i] = combine (sf[i + 1], {a[i][j], a[i][j]});
            for (int i=0; i<=N; i++)
                ok[j][i] = (pf[i].first >= lft[up] && pf[i].second <= rgt[up] &&
                    sf[i + 1].first >= lft[up ^ 1] && sf[i + 1].second <= rgt[up ^ 1]);
        }
        for (int direction = 0; direction < 2; direction ++)
        {
            for (int i=0; i<=N; i++)
                dp[1][i] = ok[1][i] | (i > 0 ? dp[1][i - 1] : 0);
            for (int i=2; i<=M; i++)
                for (int j=0; j<=N; j++)
                    dp[i][j] = (ok[i][j] & dp[i - 1][j]) | (j > 0 ? dp[i][j - 1] : 0);
            if (dp[M][N]) return 1;
            for (int i=1; i<=M; i++)
                reverse (ok[i], ok[i] + N + 1);
        }
    }
    return 0;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
    for (int j=1; j<=M; j++)
    {
        scanf ("%d", &a[i][j]);
        if (i + j == 2) mi = ma = a[i][j];
        else mi = min (mi, a[i][j]), ma = max (ma, a[i][j]);
    }
int p = (ma - mi) / 2, u = ma - mi - 1, mij, ras = ma - mi;
while (p <= u)
{
    mij = (p + u) >> 1;
    if (check (mij)) ras = mij, u = mij - 1;
    else p = mij + 1;
}
printf ("%d\n", ras);
return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 624 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Incorrect 2 ms 812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 624 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Incorrect 2 ms 812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 624 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Incorrect 2 ms 812 KB Output isn't correct
5 Halted 0 ms 0 KB -