oj.uz

Submission #76331

# Submission time Handle Problem Language Result Execution time Memory
76331 2018-09-12T16:13:44 Z win11905 Watching (JOI13_watching) C++11
100 / 100
 820 ms 8800 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3+5;

int n, p, q;
int A[N];
int dp[N][N];

bool f(int m) {
    for(int i = 0; i <= p; ++i) for(int j = 0; j <= q; ++j) {
        if(i == 0 and j == 0) continue;
        dp[i][j] = 0;
        if(i != 0) dp[i][j] = upper_bound(A+1, A+n+1, A[dp[i-1][j]+1] + m - 1) - A - 1;
        if(j != 0) dp[i][j] = max((long int)dp[i][j], upper_bound(A+1, A+n+1, A[dp[i][j-1]+1] + m + m - 1) - A - 1);
        if(dp[i][j] == n) return true;
    }
    return false;
}

int main() {
    scanf("%d %d %d", &n, &p, &q);
    if(p + q >= n) return puts("1"), 0;
    for(int i = 1; i <= n; ++i) scanf("%d", A+i);
    sort(A+1, A+n+1);
    vector<int> ret;
    for(int i = 2; i <= n; ++i) ret.emplace_back(A[i] - A[i-1]);
    sort(ret.begin(), ret.end());
    int l = 1, r = 0;
    for(int i = 0; i < n - (p+q); ++i) r += ret[i];
    while(l < r) {
        int m = l + r >> 1;
        if(f(m)) r = m;
        else l = m+1;
    }
    return !printf("%d\n", r);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                 ~~^~~
watching.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &p, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:24:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", A+i);
                                 ~~~~~^~~~~~~~~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 185 ms 1496 KB Output is correct
9 Correct 125 ms 4064 KB Output is correct
10 Correct 33 ms 8800 KB Output is correct
11 Correct 99 ms 8800 KB Output is correct
12 Correct 820 ms 8800 KB Output is correct
13 Correct 3 ms 8800 KB Output is correct
14 Correct 4 ms 8800 KB Output is correct
15 Correct 3 ms 8800 KB Output is correct