oj.uz

Submission #63494

# Submission time Handle Problem Language Result Execution time Memory
63494 2018-08-02T01:37:48 Z mra2322001 Watching (JOI13_watching) C++14
100 / 100
 531 ms 16712 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 2002;

int n, f[N][N];
int a[N], huge, tiny;
int lon[N], nho[N];

bool check(int mid){
    f1(i, n){
        int vt = lower_bound(a + 1, a + n + 1, a[i] - mid + 1) - a;
        int vt2 = lower_bound(a + 1, a + n + 1, a[i] - 2*mid + 1) - a;
        lon[i] = vt2;
        nho[i] = vt;
    }
    f0(i, tiny + 1) f[0][i] = 0;
    f1(i, n){
        f0(j, tiny + 1){
            /// nho
            int k = nho[i] - 1;
            if(j > 0){
                f[i][j] = min(f[i][j], f[k][j - 1]);
            }
            k = lon[i] - 1;
            int g = f[k][j] + 1;
            if(g > huge) g = 1e9;
            f[i][j] = min(f[i][j], g);
        }
    }
    f0(j, tiny + 1) if(f[n][j] <= huge) return 1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> tiny >> huge;
    f1(i, n) cin >> a[i];
    if(tiny + huge >= n){
        cout << 1;
        return 0;
    }

    sort(a + 1, a + n + 1);
    int l = 1, r = 1e9 + 2, ans = r;

    while(l <= r){
        int mid = (l + r)/2;
        f1(i, n) f0(j, tiny + 1) f[i][j] = 1e9;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 992 KB Output is correct
8 Correct 3 ms 992 KB Output is correct
9 Correct 3 ms 996 KB Output is correct
10 Correct 2 ms 1128 KB Output is correct
11 Correct 4 ms 1128 KB Output is correct
12 Correct 3 ms 1140 KB Output is correct
13 Correct 3 ms 1144 KB Output is correct
14 Correct 3 ms 1148 KB Output is correct
15 Correct 3 ms 1152 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8836 KB Output is correct
2 Correct 2 ms 8836 KB Output is correct
3 Correct 3 ms 8836 KB Output is correct
4 Correct 3 ms 8836 KB Output is correct
5 Correct 3 ms 8836 KB Output is correct
6 Correct 3 ms 8836 KB Output is correct
7 Correct 19 ms 9144 KB Output is correct
8 Correct 47 ms 9868 KB Output is correct
9 Correct 227 ms 14924 KB Output is correct
10 Correct 531 ms 16712 KB Output is correct
11 Correct 50 ms 16712 KB Output is correct
12 Correct 257 ms 16712 KB Output is correct
13 Correct 26 ms 16712 KB Output is correct
14 Correct 24 ms 16712 KB Output is correct
15 Correct 25 ms 16712 KB Output is correct