oj.uz

Submission #958882

# Submission time Handle Problem Language Result Execution time Memory
958882 2024-04-07T02:19:31 Z Pring Watching (JOI13_watching) C++17
100 / 100
 785 ms 31444 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx","popcnt","sse4","abm")
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 2005, MXC = 1000000005;
int n, X, Y, a[MXN];
int dp[MXN][MXN], l[MXN], l2[MXN];
deque<pii> dq, dq2;

void PRE(int w) {
    int p = 0, pp = 0;
    FOR(i, 1, n + 1) {
        while (a[i] - a[p] >= w) p++;
        while (a[i] - a[pp] >= 2 * w) pp++;
        l[i] = p - 1;
        l2[i] = pp - 1;
    }
}

bool check(int w) {
    PRE(w);
    dp[0][0] = 0;
    FOR(j, 1, n + 1) dp[0][j] = dp[0][l2[j]] + 1;
    auto POP = [&](deque<pii> &dq, int t) -> void {
        while (dq.size() && dq.front().fs < t) dq.pop_front();
    };
    auto PUSH = [&](deque<pii> &dq, int id, int val) -> void {
        while (dq.size() && dq.back().sc >= val) dq.pop_back();
        dq.push_back(mp(id, val));
    };
    FOR(i, 1, X + 1) {
        dp[i][0] = 0;
        dq.clear();
        dq2.clear();
        PUSH(dq, 0, 0);
        PUSH(dq2, 0, 0);
        FOR(j, 1, n + 1) {
            POP(dq, l[j]);
            POP(dq2, l2[j]);
            dp[i][j] = min(dq.front().sc, dq2.front().sc + 1);
            PUSH(dq, j, dp[i - 1][j]);
            PUSH(dq2, j, dp[i][j]);
        }
        if (dp[i][n] <= Y) return true;
    }
    return false;
}

void miku() {
    cin >> n >> X >> Y;
    FOR(i, 1, n + 1) cin >> a[i];
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - (a + 1);
    if (X + Y >= n) {
        cout << 1 << '\n';
        return;
    }
    a[0] = -2 * MXC;
    int l = 0, r = MXC;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        (check(mid) ? r : l) = mid;
    }
    cout << r << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 10 ms 2652 KB Output is correct
8 Correct 60 ms 2708 KB Output is correct
9 Correct 389 ms 12968 KB Output is correct
10 Correct 785 ms 31444 KB Output is correct
11 Correct 15 ms 2648 KB Output is correct
12 Correct 303 ms 17076 KB Output is correct
13 Correct 8 ms 2652 KB Output is correct
14 Correct 16 ms 2652 KB Output is correct
15 Correct 11 ms 2648 KB Output is correct