oj.uz

답안 #939987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939987 2024-03-07T03:24:33 Z qwe1rt1yuiop1 The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
// #define int long long
using namespace std;

int n, m, mx, mn;
vector<vector<int>> v;

int f1(int mid)
{
    vector<int> tmp(n);
    int x = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = m - 1;
        for (; cur >= 0; --cur)
            if (v[i][cur] < mx - mid)
                break;
        ++cur;
        x = max(x, cur);
        tmp[i] = x;
        for (int j = 0; j < x; ++j)
            if (v[i][j] > mn + mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < tmp[i]; ++j)
            assert(v[i][j] <= mn + mid);
        for (int j = tmp[i]; j < m; ++j)
            assert(v[i][j] >= mx - mid);
    }
    return 1;
}

int f2(int mid)
{
    vector<int> tmp(n);
    int x = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = m - 1;
        for (; cur >= 0; --cur)
            if (v[i][cur] > mn + mid)
                break;
        ++cur;
        x = max(x, cur);
        tmp[i] = x;
        for (int j = 0; j < x; ++j)
            if (v[i][j] < mx - mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < tmp[i]; ++j)
            assert(v[i][j] >= mx - mid);
        for (int j = tmp[i]; j < m; ++j)
            assert(v[i][j] <= mn + mid);
    }
    return 1;
}

int f3(int mid)
{
    vector<int> tmp(n);
    int x = m - 1;
    for (int i = 0; i < n; ++i)
    {
        int cur = 0;
        for (; cur < m; ++cur)
            if (v[i][cur] < mx - mid)
                break;
        --cur;
        x = min(x, cur);
        tmp[i] = x;
        for (int j = cur + 1; j < m; ++j)
            if (v[i][j] > mn + mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= tmp[i]; ++j)
            assert(v[i][j] >= mx - mid);
        for (int j = tmp[i] + 1; j < m; ++j)
            assert(v[i][j] <= mn + mid);
    }
    return 1;
}

int f4(int mid)
{
    vector<int> tmp(n);
    int x = m - 1;
    for (int i = 0; i < n; ++i)
    {
        int cur = 0;
        for (; cur < m; ++cur)
            if (v[i][cur] > mn + mid)
                break;
        --cur;
        x = min(x, cur);
        tmp[i] = x;
        for (int j = cur + 1; j < m; ++j)
            if (v[i][j] < mx - mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= tmp[i]; ++j)
            assert(v[i][j] <= mn + mid);
        for (int j = tmp[i] + 1; j < m; ++j)
            assert(v[i][j] >= mx - mid);
            // if(v[i][j] >= mx - mid)
            // {
            //     cout << mid << ' ' << i << ' ' << j << ' ' << tmp[i] << '\n';
            // }
    }
    return 1;
}

void solve()
{
    cin >> n >> m;
    v.assign(n, vector<int>(m));
    mx = 0, mn = INT_MAX;
    for (auto &i : v)
        for (auto &j : i)
            cin >> j, mx = max(mx, j), mn = min(mn, j);

    int l = 0, r = 1000000005;
    while (l < r)
    {
        int mid = (l + r) >> 1;

        if (f1(mid) || f2(mid) || f3(mid) || f4(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << '\n';
}

/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16

 */

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -