oj.uz

답안 #40349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40349 2018-01-31T08:48:34 Z krauch 구경하기 (JOI13_watching) C++14
100 / 100
 172 ms 9192 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

const ll ool = 1e18 + 9;
const int N = 3e3 + 3, oo = 1e9 + 9;

int n, P, Q, a[N], d[N][N];

bool check(int W) {
    int ptr = 1;
    forn(i, 0, P) forn(j, 0, Q) d[i][j] = 1;
    forn(i, 0, P) {
        forn(j, 0, Q) {
            if (d[i][j] == -1) continue;
            int ptr = d[i][j];
            while (ptr <= n && a[ptr] - a[d[i][j]] + 1 <= W) {
                ++ptr;
            }
            d[i + 1][j] = max(d[i + 1][j], ptr);
            while (ptr <= n && a[ptr] - a[d[i][j]] + 1 <= 2 * W) {
                ++ptr;
            }
            d[i][j + 1] = max(d[i][j + 1], ptr);
        }
    }
    return (d[P][Q] == n + 1);
}

int main() {

    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    cin >> n >> P >> Q;
    Q = min(Q, n);
    P = min(P, n - Q);
    forn(i, 1, n) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    int l = 1, r = a[n];
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << "\n";

    return 0;
}

Compilation message

watching.cpp: In function 'bool check(int)':
watching.cpp:23:9: warning: unused variable 'ptr' [-Wunused-variable]
     int ptr = 1;
         ^

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 800 KB Output is correct
5 Correct 1 ms 800 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 1 ms 800 KB Output is correct
9 Correct 2 ms 800 KB Output is correct
10 Correct 2 ms 800 KB Output is correct
11 Correct 2 ms 908 KB Output is correct
12 Correct 2 ms 908 KB Output is correct
13 Correct 1 ms 908 KB Output is correct
14 Correct 1 ms 908 KB Output is correct
15 Correct 1 ms 908 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 908 KB Output is correct
2 Correct 2 ms 908 KB Output is correct
3 Correct 128 ms 5688 KB Output is correct
4 Correct 38 ms 9056 KB Output is correct
5 Correct 3 ms 9056 KB Output is correct
6 Correct 3 ms 9056 KB Output is correct
7 Correct 3 ms 9056 KB Output is correct
8 Correct 26 ms 9056 KB Output is correct
9 Correct 30 ms 9056 KB Output is correct
10 Correct 42 ms 9192 KB Output is correct
11 Correct 33 ms 9192 KB Output is correct
12 Correct 172 ms 9192 KB Output is correct
13 Correct 3 ms 9192 KB Output is correct
14 Correct 3 ms 9192 KB Output is correct
15 Correct 3 ms 9192 KB Output is correct