oj.uz

Submission #136460

# Submission time Handle Problem Language Result Execution time Memory
136460 2019-07-25T10:31:28 Z egorlifar Watching (JOI13_watching) C++17
100 / 100
 452 ms 16248 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 2005;

int n, p, q;
int a[MAXN];
int pos[MAXN], pos1[MAXN];
int dp[MAXN][MAXN];


bool can(int x) {
    int uk = 0;
    for (int i = 0; i < n; i++) {
        while (uk + 1 < n && a[i] + x - 1 >= a[uk + 1]) {
            uk++;
        }
        pos[i] = uk;
    }
    uk = 0;
    for (int i = 0; i < n; i++) {
        while (uk + 1 < n && a[i] + 2 * x - 1 >= a[uk + 1]) {
            uk++;
        }
        pos1[i] = uk;
    }
    if (p + q >= n) {
        return true;
    }
    for (int i = 0; i <= n; i++) {
        for (int cnt = 0; cnt <= p; cnt++) {
            dp[i][cnt] = 1e9;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int cnt = 0; cnt <= p; cnt++) {
            if (cnt + 1 <= p) {
                chkmin(dp[pos[i] + 1][cnt + 1], dp[i][cnt]);
            }
            chkmin(dp[pos1[i] + 1][cnt], dp[i][cnt] + 1);
        }
    }
    for (int cnt = 0; cnt <= p; cnt++) {
        if (dp[n][cnt] <= q) {
            return true;
        }
    }
    return false;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // read(FILENAME); 
    cin >> n >> p >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int l = 1;
    int r = 1000000000;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (can(mid)) {
            r = mid; 
        } else {
            l = mid + 1;
        }
    }
    cout << l << '\n';
    return 0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8312 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 15 ms 8568 KB Output is correct
8 Correct 43 ms 9336 KB Output is correct
9 Correct 183 ms 14332 KB Output is correct
10 Correct 452 ms 16248 KB Output is correct
11 Correct 38 ms 9208 KB Output is correct
12 Correct 270 ms 16148 KB Output is correct
13 Correct 16 ms 8440 KB Output is correct
14 Correct 17 ms 8568 KB Output is correct
15 Correct 14 ms 8568 KB Output is correct