oj.uz

답안 #473039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473039 2021-09-14T19:24:10 Z nicolaalexandra 구경하기 (JOI13_watching) C++14
0 / 100
 140 ms 15948 KB 
#include <bits/stdc++.h>
#define DIM 2010
#define INF 1000000000
using namespace std;

int v[DIM],dp[DIM][DIM];
int n,p,q,i;

int get_poz (int x){
    int st = 1, dr = n, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] >= x){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }
    return sol;
}


int verif (int val){

    for (int i=1;i<=n;i++)
        for (int j=0;j<=n;j++)
            dp[i][j] = INF;

    for (int i=1;i<=n;i++){

        int poz = get_poz (v[i] - val + 1);
        int poz2 = get_poz (v[i] - 2 * val + 1);

        for (int j=1;j<=p;j++)
            dp[i][j] = min (dp[poz-1][j-1], dp[poz2-1][j] + 1);
    }

    if (dp[n][p] <= q)
        return 1;
    return 0;
}


int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>p>>q;
    for (i=1;i<=n;i++)
        cin>>v[i];

    sort (v+1,v+n+1);
    p = min (p,n), q = min (q,n);

    int st = 0, dr = INF, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    cout<<sol;

    return 0;
}

Subtask #1
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 15948 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -