답안 #87903 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87903	2018-12-03T04:58:20 Z	tieunhi	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2285 ms	53992 KB

joioi

#include <bits/stdc++.h>
#define pii pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define N 2003
#define LN 19
#define maxc 1000000007

using namespace std;

int n, m, a[N][N], amin, amax, pos[N];
bool b[N][N];
void revRow()
{
    FOR(i, 1, n)
        FOR(j, 1, m/2)
            swap(a[i][j], a[i][m-j+1]);
}
void revCol()
{
    FOR(j, 1, m)
        FOR(i, 1, n/2)
            swap(a[i][j], a[n-i+1][j]);
}
bool ok(int diff)
{
    FOR(i, 1, n)
        FOR(j, 1, m)
            b[i][j] = (a[i][j] >= (amax - diff));
    pos[0] = m;
    FOR(i, 1, n)
    {
        pos[i] = pos[i-1];
        FOR(j, 1, pos[i-1])
            if (b[i][j] == 0) {pos[i] = j-1; break;}
    }
    int mx = 0, mn = maxc;
    if (pos[n] == m) return 1;
    FOR(i, 1, n)
        FOR(j, pos[i]+1, m)
        {
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
        }
    if (abs(mx - mn) <= diff) return 1;
    return 0;
}
bool check(int diff)
{

    if (ok(diff)) return 1;
    revRow();
    if (ok(diff)) return 1;
    revCol();
    if (ok(diff)) return 1;
    revRow();
    if (ok(diff)) return 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> m;
    amin = maxc, amax = 0;
    FOR(i, 1, n)
        FOR(j, 1, m)
        {
            cin >> a[i][j];
            amax = max(amax, a[i][j]);
            amin = min(amin, a[i][j]);
        }
    int l = 0, r = amax - amin + 1;
    while (r - l > 1)
    {
        int mid = (r + l)/2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout <<r;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	644 KB	Output is correct
6	Correct	2 ms	644 KB	Output is correct
7	Correct	3 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	2 ms	644 KB	Output is correct
10	Correct	3 ms	752 KB	Output is correct
11	Correct	2 ms	752 KB	Output is correct
12	Correct	2 ms	752 KB	Output is correct
13	Correct	2 ms	752 KB	Output is correct
14	Correct	2 ms	752 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	644 KB	Output is correct
6	Correct	2 ms	644 KB	Output is correct
7	Correct	3 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	2 ms	644 KB	Output is correct
10	Correct	3 ms	752 KB	Output is correct
11	Correct	2 ms	752 KB	Output is correct
12	Correct	2 ms	752 KB	Output is correct
13	Correct	2 ms	752 KB	Output is correct
14	Correct	2 ms	752 KB	Output is correct
15	Correct	2 ms	752 KB	Output is correct
16	Correct	7 ms	2104 KB	Output is correct
17	Correct	14 ms	2308 KB	Output is correct
18	Correct	16 ms	2580 KB	Output is correct
19	Correct	15 ms	2976 KB	Output is correct
20	Correct	13 ms	3120 KB	Output is correct
21	Correct	19 ms	3488 KB	Output is correct
22	Correct	21 ms	3976 KB	Output is correct
23	Correct	17 ms	4260 KB	Output is correct
24	Correct	18 ms	4520 KB	Output is correct
25	Correct	18 ms	5028 KB	Output is correct
26	Correct	19 ms	5380 KB	Output is correct
27	Correct	21 ms	5768 KB	Output is correct
28	Correct	20 ms	6176 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	644 KB	Output is correct
6	Correct	2 ms	644 KB	Output is correct
7	Correct	3 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	2 ms	644 KB	Output is correct
10	Correct	3 ms	752 KB	Output is correct
11	Correct	2 ms	752 KB	Output is correct
12	Correct	2 ms	752 KB	Output is correct
13	Correct	2 ms	752 KB	Output is correct
14	Correct	2 ms	752 KB	Output is correct
15	Correct	2 ms	752 KB	Output is correct
16	Correct	7 ms	2104 KB	Output is correct
17	Correct	14 ms	2308 KB	Output is correct
18	Correct	16 ms	2580 KB	Output is correct
19	Correct	15 ms	2976 KB	Output is correct
20	Correct	13 ms	3120 KB	Output is correct
21	Correct	19 ms	3488 KB	Output is correct
22	Correct	21 ms	3976 KB	Output is correct
23	Correct	17 ms	4260 KB	Output is correct
24	Correct	18 ms	4520 KB	Output is correct
25	Correct	18 ms	5028 KB	Output is correct
26	Correct	19 ms	5380 KB	Output is correct
27	Correct	21 ms	5768 KB	Output is correct
28	Correct	20 ms	6176 KB	Output is correct
29	Correct	1277 ms	45676 KB	Output is correct
30	Correct	1127 ms	53816 KB	Output is correct
31	Correct	1160 ms	53816 KB	Output is correct
32	Correct	1439 ms	53916 KB	Output is correct
33	Correct	1184 ms	53916 KB	Output is correct
34	Correct	1184 ms	53916 KB	Output is correct
35	Correct	2285 ms	53992 KB	Output is correct
36	Correct	1776 ms	53992 KB	Output is correct
37	Correct	1956 ms	53992 KB	Output is correct

답안 #87903

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0