제출 #363517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363517		cute_hater	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2790 ms	53228 KiB

joioi

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No"; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 2007;

int f[N][N], up[N];

int calc_ans(int n, int m, int mn, int mx) {
    up[0] = n + 1;
    loop1(j, m) {
        up[j] = n + 1;
        loop1(i, n) {
            if (f[i][j] == mx) {
                up[j] = i; break;
            }
        }
    }
    loop1(j, m)
        up[j] = min(up[j], up[j - 1]);
    int cur = 0;
    loop1(j, m)
        for (int i = up[j]; i <= n; ++i)
            cur = max(cur, mx - f[i][j]);
    int l = cur - 1, r = mx - mn;
    while (r - l > 1) {
        int mid = l + r >> 1;
        bool flag = 1;
        int cur = 1;
        for (int j = m; j > 0; --j) {
            int i = up[j] - 1;
            for (; i >= cur && mx - f[i][j] <= mid; --i);
            loop1(k, i)
                if (f[k][j] - mn > mid)
                    flag = 0;
            cur = i + 1;
        }
        if (flag)
            r = mid;
        else
            l = mid;
    }
    return r;
}

void solve() {
    int n, m;
    cin >> n >> m;
    int mx = 0, mn = 1000000000;
    loop1(i, n) {
        loop1(j, m) {
            cin >> f[i][j];
            mn = min(mn, f[i][j]);
            mx = max(mx, f[i][j]);
        }
    }
    int ans = calc_ans(n, m, mn, mx);
    loop1(j, m)
        loop1(i, n / 2)
            swap(f[i][j], f[n - i + 1][j]);
    ans = min(ans, calc_ans(n, m, mn, mx));
    loop1(i, n)
        loop1(j, m / 2)
            swap(f[i][j], f[i][m - j + 1]);
    ans = min(ans, calc_ans(n, m, mn, mx));
    loop1(j, m)
        loop1(i, n / 2)
            swap(f[i][j], f[n - i + 1][j]);
    ans = min(ans, calc_ans(n, m, mn, mx));
    cout << ans;
}

signed main() {
    //freopen("dream.in", "r", stdin);
    //freopen("dream.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'll calc_ans(ll, ll, ll, ll)':
joioi.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid = l + r >> 1;
      |                   ~~^~~

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