oj.uz

Submission #107754

# Submission time Handle Problem Language Result Execution time Memory
107754 2019-04-25T16:15:38 Z tieunhi Watching (JOI13_watching) C++14
100 / 100
 339 ms 16248 KB 
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define ll long long
#define N 2005
#define maxc 1000000007

using namespace std;

int dp[N][N];
int n, P, Q;
vector<int> a;
bool check(int len) {
    memset(dp, 60, sizeof dp);
    dp[0][0] = 0;
    FOR(i, 1, n)
    {
        int x1 = a[i] - len + 1;
        int pos1 = lower_bound(a.begin(), a.end(), x1) - a.begin() - 1;

        int x2 = a[i] - 2*len + 1;
        int pos2 = lower_bound(a.begin(), a.end(), x2) - a.begin() - 1;


        FOR(j, 0, P) {
            if (j) dp[i][j] = min(dp[i][j], dp[pos1][j-1]);
            dp[i][j] = min(dp[i][j], dp[pos2][j] + 1);
        }
    }
    FOR(j, 0, P)
        if (dp[n][j] <= Q) 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 >> P >> Q;
    if (P + Q >= n) {
        cout <<1;
        return 0;
    }


    FOR(i, 1, n) {
        int x; cin >> x;
        a.PB(x);
    }
    a.PB(-2*maxc);

    sort(a.begin(), a.end());
    int L = 0, R = maxc;
    while (R - L > 1) {
        int mid = (R + L)/2;
        if (check(mid)) R = mid;
        else L = mid;
    }
    cout <<R;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 16000 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 103 ms 16108 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 113 ms 16108 KB Output is correct
8 Correct 115 ms 16120 KB Output is correct
9 Correct 119 ms 16172 KB Output is correct
10 Correct 104 ms 16112 KB Output is correct
11 Correct 106 ms 16220 KB Output is correct
12 Correct 125 ms 16092 KB Output is correct
13 Correct 105 ms 16128 KB Output is correct
14 Correct 106 ms 16128 KB Output is correct
15 Correct 120 ms 16248 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 16128 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 119 ms 16248 KB Output is correct
8 Correct 145 ms 16128 KB Output is correct
9 Correct 240 ms 16128 KB Output is correct
10 Correct 339 ms 16248 KB Output is correct
11 Correct 156 ms 16248 KB Output is correct
12 Correct 262 ms 16248 KB Output is correct
13 Correct 133 ms 16220 KB Output is correct
14 Correct 141 ms 16220 KB Output is correct
15 Correct 121 ms 16128 KB Output is correct