oj.uz

Submission #59379

# Submission time Handle Problem Language Result Execution time Memory
59379 2018-07-21T21:41:54 Z FLDutchman Watching (JOI13_watching) C++14
100 / 100
 843 ms 32496 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define MMAX 16384
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 2e3+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

int w, N, P, Q;
vi A;

int dp2[NMAX][2];
int ub(int i, bool d){
    int &res = dp2[i][d];
    if(res != -1) return res;
    if(d) return res = upper_bound(A.begin(), A.end(), A[i]+2*w-1) - A.begin();
    else return res = upper_bound(A.begin(), A.end(), A[i]+  w-1) - A.begin();
}

int dp[NMAX][NMAX];
int leastQ(int i, int p){
    //cout << i << " " << p << endl;
    if(p < 0) return INF;
    int &res = dp[i][p];
    if(res != -1) return res;
    if(i == N) return res = 0;
    res = INF;
    res = min(res,     leastQ(ub(i, 0), p-1));
    res = min(res, 1 + leastQ(ub(i, 1), p  ));
    return res;
}

signed main(){
    fast_io();
    cin >> N >> P >> Q;
    A.resize(N);
    FOR(i, 0, N) cin >> A[i];
    sort(A.begin(), A.end());
    if(P+Q >= N) {
        cout << 1 << endl;
        return 0;
    }


    int lb = 0, rb = 1e9;
    while(lb+1 != rb){
        FOR(i, 0, NMAX) FOR(j, 0, NMAX) dp[i][j] = -1;
        FOR(i, 0, NMAX) FOR(j, 0, 2) dp2[i][j] = -1;
        w = (lb+rb)/2;
        if(leastQ(0, P) <= Q) rb = w;
        else lb = w;
    }
    cout << rb << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 31992 KB Output is correct
2 Correct 3 ms 31992 KB Output is correct
3 Correct 220 ms 31992 KB Output is correct
4 Correct 2 ms 31992 KB Output is correct
5 Correct 3 ms 31992 KB Output is correct
6 Correct 3 ms 31992 KB Output is correct
7 Correct 196 ms 31992 KB Output is correct
8 Correct 214 ms 32036 KB Output is correct
9 Correct 229 ms 32036 KB Output is correct
10 Correct 221 ms 32036 KB Output is correct
11 Correct 218 ms 32180 KB Output is correct
12 Correct 222 ms 32180 KB Output is correct
13 Correct 229 ms 32212 KB Output is correct
14 Correct 212 ms 32212 KB Output is correct
15 Correct 221 ms 32212 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 32224 KB Output is correct
2 Correct 3 ms 32224 KB Output is correct
3 Correct 3 ms 32224 KB Output is correct
4 Correct 3 ms 32224 KB Output is correct
5 Correct 4 ms 32224 KB Output is correct
6 Correct 4 ms 32224 KB Output is correct
7 Correct 243 ms 32224 KB Output is correct
8 Correct 285 ms 32224 KB Output is correct
9 Correct 378 ms 32236 KB Output is correct
10 Correct 843 ms 32496 KB Output is correct
11 Correct 274 ms 32496 KB Output is correct
12 Correct 604 ms 32496 KB Output is correct
13 Correct 220 ms 32496 KB Output is correct
14 Correct 192 ms 32496 KB Output is correct
15 Correct 202 ms 32496 KB Output is correct