oj.uz

Submission #481319

# Submission time Handle Problem Language Result Execution time Memory
481319 2021-10-20T11:16:37 Z Alexandruabcde Watching (JOI13_watching) C++14
100 / 100
 198 ms 16068 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2005;

int N, P, Q;
int A[NMAX];
int dp[NMAX][NMAX];

bool Check (int W) {
    for (int i = 0; i <= N; ++ i )
        for (int j = 0; j <= N; ++ j )
            dp[i][j] = 0;

    int last_p = 1, last_q = 1;
    for (int i = 1; i <= N; ++ i ) {
        while (last_p < i && A[i] - A[last_p] + 1 > W)
            ++ last_p;

        while (last_q < i && A[i] - A[last_q] + 1 > 2*W)
            ++ last_q;

        dp[i][0] = dp[last_q-1][0] + 1;
        for (int j = 1; j <= min(P, N); ++ j )
            dp[i][j] = min(dp[last_q-1][j] + 1, dp[last_p-1][j-1]);
    }

    for (int i = 0; i <= min(P, N); ++ i )
        if (dp[N][i] <= Q)
            return 1;

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> P >> Q;

    for (int i = 1; i <= N; ++ i )
        cin >> A[i];
    sort(A+1, A+N+1);

    int st = 1, dr = 1e9;
    int ans = 0;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (Check(mij)) {
            ans = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    cout << ans << '\n';
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 704 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 704 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 708 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 708 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15948 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 174 ms 15948 KB Output is correct
4 Correct 194 ms 16036 KB Output is correct
5 Correct 81 ms 16024 KB Output is correct
6 Correct 198 ms 16032 KB Output is correct
7 Correct 68 ms 16028 KB Output is correct
8 Correct 79 ms 16036 KB Output is correct
9 Correct 133 ms 16068 KB Output is correct
10 Correct 198 ms 15948 KB Output is correct
11 Correct 72 ms 15948 KB Output is correct
12 Correct 148 ms 16028 KB Output is correct
13 Correct 81 ms 15948 KB Output is correct
14 Correct 70 ms 16028 KB Output is correct
15 Correct 78 ms 15948 KB Output is correct