제출 #568190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568190		gg123_pe	구경하기 (JOI13_watching)	C++14	100 / 100	217 ms	16204 KiB

watching

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,ll> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

#define ff first 
#define ss second 

const int N = 2005; 
const ll inf = 1e17 + 100; 


int n, p, q, dp[N][N]; 
int a[N], idw[N], id2w[N]; 

void go(int w){
    queue <pair<int,int>> q1, q2; 
    
    f(i,1,n+1){
        q1.push({a[i], i}); q2.push({a[i], i}); 

        while(a[i] - q1.front().first > w-1) q1.pop(); 
        idw[i] = q1.front().second; 

        while(a[i] - q2.front().first > 2*w-1) q2.pop();
        id2w[i] = q2.front().second; 
    }

    f(i,1,n+1) f(j,0,n) dp[i][j] = 0; 

    f(i,1,n+1){
        dp[i][0] = dp[id2w[i] - 1][0] + 1; 
        f(j,1,n){
            dp[i][j] = min(dp[idw[i] - 1][j-1], dp[id2w[i] - 1][j] + 1); 
        }
    }
}   
int main(){
    cin >> n >> p >> q; 
    set <int> s; 

    f(i,1,n+1){
        int x; cin >> x; 
        s.insert(x); 
    }

    n = 0; 
    for(int x: s) a[++n] = x; 

    int l = 1, r = 1000000000; 
    while(l < r){
        int m = (l+r)>>1; 
        go(m); 
        if(p >= n or dp[n][p] <= q) r = m; 
        else l = m+1; 
    } 
    cout << l << "\n"; 
    return 0; 
}

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