oj.uz

Submission #363517

# Submission time Handle Problem Language Result Execution time Memory
363517 2021-02-06T10:30:57 Z cute_hater The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 2790 ms 53228 KB 
#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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 4 ms 1516 KB Output is correct
17 Correct 6 ms 1772 KB Output is correct
18 Correct 7 ms 1772 KB Output is correct
19 Correct 7 ms 1772 KB Output is correct
20 Correct 6 ms 1536 KB Output is correct
21 Correct 7 ms 1772 KB Output is correct
22 Correct 8 ms 1772 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 8 ms 1644 KB Output is correct
25 Correct 9 ms 1772 KB Output is correct
26 Correct 9 ms 1772 KB Output is correct
27 Correct 8 ms 1772 KB Output is correct
28 Correct 9 ms 1772 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 4 ms 1516 KB Output is correct
17 Correct 6 ms 1772 KB Output is correct
18 Correct 7 ms 1772 KB Output is correct
19 Correct 7 ms 1772 KB Output is correct
20 Correct 6 ms 1536 KB Output is correct
21 Correct 7 ms 1772 KB Output is correct
22 Correct 8 ms 1772 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 8 ms 1644 KB Output is correct
25 Correct 9 ms 1772 KB Output is correct
26 Correct 9 ms 1772 KB Output is correct
27 Correct 8 ms 1772 KB Output is correct
28 Correct 9 ms 1772 KB Output is correct
29 Correct 1051 ms 35680 KB Output is correct
30 Correct 1012 ms 53228 KB Output is correct
31 Correct 1052 ms 37740 KB Output is correct
32 Correct 883 ms 37768 KB Output is correct
33 Correct 799 ms 47980 KB Output is correct
34 Correct 1004 ms 38380 KB Output is correct
35 Correct 2563 ms 41252 KB Output is correct
36 Correct 2021 ms 39784 KB Output is correct
37 Correct 2790 ms 41580 KB Output is correct