Submission #490743

#	Time	Username	Problem	Language	Result	Execution time	Memory
490743		uHyHn	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2394 ms	102288 KiB

joioi

#include<bits/stdc++.h>

//IBOW
#define Task "KOJOIOI"
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define rep(i, b) for (int i = (1); i <= (b); ++i)
#define REP(i, b) for (int i = (b); i >= (1); --i)
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define eb emplace_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<long long> vll;

const int N = 2e3 + 10;
const int inf = 2e9 + 10;
const ll INF = 2e18 + 10;
const int MOD = 1e9 + 7;

int n, m, a[N][N], okA[N][N], okB[N][N], min_value = inf, max_value = 0, suf[N][N], pre[N][N];

bool ok(ll v)
{
    fill(&suf[0][0], &suf[0][0] + N * N, 0);
    fill(&pre[0][0], &pre[0][0] + N * N, 0);
    rep(i, n) rep(j, m) okA[i][j] = okB[i][j] = 0;
    rep(i, n) rep(j, m)
    {
        if (a[i][j] - min_value <= v) okA[i][j] = 1;
        if (max_value <= v + a[i][j]) okB[i][j] = 1;
    }
//    rep(i, n) rep(j, m) cout << okA[i][j] << " \n"[j == m];
//    cout << '\n';
//    rep(i, n) rep(j, m) cout << okB[i][j] << " \n"[j == m];
    {
        //phần A ở trên phần B ở dưới
        rep(i, n)
        {
            rep(j, m) pre[i][j] = pre[i][j - 1] + okA[i][j];
            REP(j, m) suf[i][j] = suf[i][j + 1] + okB[i][j];
        }
        {
            //phần A tăng dần
            int past_height = 0;
            rep(i, n)
            {
                bool flag = false;
                if (i == n)
                {
                    rep(j, m)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                } else
                {
                    for (int j = 0; j <= m; ++j)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                }
                if (flag)
                {
                    if (i == n)
                    {
//                        cout << 1 << '\n';
                        return true;
                    }
                    continue;
                }
                else break;
            }
        }
        {
            //Phần A giảm dần
            int past_height = 0;
            REP(i, n)
            {
                bool flag = false;
                if (i == 1)
                {
                    rep(j, m)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                } else
                {
                    for (int j = 0; j <= m; ++j)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                }
                if (flag)
                {
                    if (i == 1)
                    {
//                        cout << 2 << '\n';
                        return true;
                    }
                    continue;
                }
                else break;
            }
        }
    }
    {
        //Phần B ở trên phần A ở dưới
        fill(&suf[0][0], &suf[0][0] + N * N, 0);
        fill(&pre[0][0], &pre[0][0] + N * N, 0);
        rep(i, n)
        {
            rep(j, m) pre[i][j] = pre[i][j - 1] + okB[i][j];
            REP(j, m) suf[i][j] = suf[i][j + 1] + okA[i][j];
        }
        {
            //phần B tăng dần
            int past_height = 0;
            rep(i, n)
            {
                bool flag = false;
                if (i == n)
                {
                    rep(j, m)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                } else
                {
                    for (int j = 0; j <= m; ++j)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                }
                if (flag)
                {
                    if (i == n)
                    {
//                        cout << 3 << '\n';
                        return true;
                    }
                    continue;
                }
                else break;
            }
        }
        {
            //Phần B giảm dần
            int past_height = 0;
            REP(i, n)
            {
                bool flag = false;
                if (i == 1)
                {
                    rep(j, m)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                } else
                {
                    for (int j = 0; j <= m; ++j)
                    {
                        if (pre[i][j] == j && suf[i][j + 1] == m - j && j >= past_height)
                        {
                            flag = true;
                            past_height = j;
                            break;
                        }
                    }
                }
                if (flag)
                {
                    if (i == 1)
                    {
//                        cout << 4 << '\n';
                        return true;
                    }
                    continue;
                }
                else break;
            }
        }
    }
    return false;
}
void DeoAClamcho()
{
    cin >> n >> m;
    rep(i, n) rep(j, m)
    {
        cin >> a[i][j];
        min_value = min(min_value, a[i][j]);
        max_value = max(max_value, a[i][j]);
    }
    ll L = 1, R = 1e9, ans = 0;
    while (L <= R)
    {
        ll mid = (L + R) / 2;
//        cout << mid << ":\n";
        if (ok(mid)) R = mid - 1, ans = mid;
        else L = mid + 1;
    }
    cout << ans;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(Task".inp", "r"))
    {
        freopen(Task".inp", "r", stdin);
//        freopen(Task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t--) DeoAClamcho();
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int32_t main()':
joioi.cpp:255:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |         freopen(Task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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