oj.uz

Submission #205600

# Submission time Handle Problem Language Result Execution time Memory
205600 2020-02-29T09:27:18 Z Kastanda The Kingdom of JOIOI (JOI17_joioi) C++11
0 / 100
 4000 ms 504 KB 
// In The Name Of The Queen
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimzie("O3")
using namespace std;
const int N = 2019, INF = 1e9 + 1;
int n, m, A[N][N], P[N], S[N], B[N];
pair < int , int > At[2];
int Val[2];
inline int Solve(int md)
{
    for (int w = 0; w <= 1; w ++)
    {
        P[0] = 0; S[m + 1] = INF;
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= m; j ++)
                P[j] = max(P[j - 1], A[i][j]);
            for (int j = m; j; j --)
                S[j] = min(S[j + 1], A[i][j]);
            B[i] = m + 1;
            int l = B[i - 1], r = m;
            if (At[0].first == i)
                l = max(l, At[0].second);
            if (At[1].first == i)
                r = min(r, At[1].second - 1);
            for (int j = l; j <= r; j ++)
            {
                if (P[j] - Val[0] > md)
                    break;
                if (Val[1] - S[j + 1] > md)
                    continue;
                B[i] = j;
                break;
            }
        }
        if (B[n] <= m)
            return 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                A[i][j] = INF - A[i][j];
        Val[0] = INF - Val[0];
        Val[1] = INF - Val[1];
        swap(Val[0], Val[1]);
        swap(At[0], At[1]);
    }
    return 0;
}
inline int Run()
{
    Val[0] = INT_MAX;
    Val[1] = INT_MIN;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            if (Val[0] > A[i][j])
                Val[0] = A[i][j], At[0] = {i, j};
            if (Val[1] < A[i][j])
                Val[1] = A[i][j], At[1] = {i, j};
        }
    int le = -1, ri = Val[1] - Val[0], md;
    while (ri - le > 1)
    {
        md = (le + ri + ri) / 3;
        if (Solve(md))
            ri = md;
        else
            le = md;
    }
    return (ri);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            scanf("%d", &A[i][j]);
    int Mn = Run();
    for (int i = 1; i < n - i + 1; i ++)
        for (int j = 1; j <= m; j ++)
            swap(A[i][j], A[n - i + 1][j]);
    Mn = min(Mn, Run());
    return !printf("%d\n", Mn);
}

Compilation message

joioi.cpp:4:0: warning: ignoring #pragma GCC optimzie [-Wunknown-pragmas]
 #pragma GCC optimzie("O3")
 
joioi.cpp: In function 'int main()':
joioi.cpp:74: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:77: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Execution timed out 4061 ms 376 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Execution timed out 4061 ms 376 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Execution timed out 4061 ms 376 KB Time limit exceeded
4 Halted 0 ms 0 KB -