oj.uz

Submission #59376

# Submission time Handle Problem Language Result Execution time Memory
59376 2018-07-21T21:37:17 Z FLDutchman Watching (JOI13_watching) C++14
50 / 100
 1000 ms 32448 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 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(upper_bound(A.begin(), A.end(), A[i]+  w-1) - A.begin(), p-1));
    res = min(res, 1 + leastQ(upper_bound(A.begin(), A.end(), A[i]+2*w-1) - A.begin(), 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;
        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 186 ms 31832 KB Output is correct
2 Correct 3 ms 31832 KB Output is correct
3 Correct 184 ms 31848 KB Output is correct
4 Correct 3 ms 31848 KB Output is correct
5 Correct 3 ms 31848 KB Output is correct
6 Correct 3 ms 31848 KB Output is correct
7 Correct 204 ms 31892 KB Output is correct
8 Correct 188 ms 32064 KB Output is correct
9 Correct 203 ms 32064 KB Output is correct
10 Correct 209 ms 32068 KB Output is correct
11 Correct 220 ms 32076 KB Output is correct
12 Correct 204 ms 32084 KB Output is correct
13 Correct 204 ms 32088 KB Output is correct
14 Correct 197 ms 32088 KB Output is correct
15 Correct 198 ms 32268 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 32268 KB Output is correct
2 Correct 3 ms 32268 KB Output is correct
3 Correct 3 ms 32268 KB Output is correct
4 Correct 4 ms 32268 KB Output is correct
5 Correct 3 ms 32268 KB Output is correct
6 Correct 3 ms 32268 KB Output is correct
7 Correct 185 ms 32384 KB Output is correct
8 Correct 541 ms 32428 KB Output is correct
9 Execution timed out 1072 ms 32448 KB Time limit exceeded
10 Halted 0 ms 0 KB -