Submission #5765

#	Time	Username	Problem	Language	Result	Execution time	Memory
5765		tncks0121	Watching (JOI13_watching)	C++98	100 / 100	328 ms	17404 KiB

watching

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <bits/stdc++.h>
#include <memory.h>

typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
typedef unsigned int uint;

using namespace std;

const int N_ = 2005;

int N, P, Q, A[N_];
int res;

int Table[N_][N_];
int X[N_], Y[N_];

bool possible (int w) {
    for(int i = 1, j = 1; i <= N; i++) {
        while(A[j] - A[i] < w && j <= N) ++j;
        X[i] = --j;
    }

    for(int i = 1, j = 1; i <= N; i++) {
        while(A[j] - A[i] < w+w && j <= N) ++j;
        Y[i] = --j;
    }

    X[N+1] = Y[N+1] = N;

    for(int i = 0; i <= P; i++) {
        for(int j = 0; j <= Q; j++) Table[i][j] = 0;
    }

    for(int i = 0; i <= P; i++) {
        for(int j = 0; j <= Q; j++) {
            if(i < P) Table[i+1][j] = max(Table[i+1][j], X[Table[i][j] + 1]);
            if(j < Q) Table[i][j+1] = max(Table[i][j+1], Y[Table[i][j] + 1]);
        }
    }

    return Table[P][Q] >= N;
}

int main() {
    scanf("%d%d%d", &N, &P, &Q);
    if(P + Q >= N) {
        puts("1");
        return 0;
    }

    for(int i = 1; i <= N; i++) scanf("%d", A+i);
    sort(A+1, A+N+1);
    N = unique(A+1, A+N+1) - (A+1);

    int low = 0, high = (int)1e9;
    while(low <= high) {
        int mid = (low + high) >> 1;
        if(possible(mid)) {
            res = mid;
            high = mid - 1;
        }else {
            low = mid + 1;
        }
    }

    printf("%d\n", res);
    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50