제출 #1355122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355122		takoshanava	구경하기 (JOI13_watching)	C++20	100 / 100	142 ms	31864 KiB

watching

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 2005;
int dp[N][N], a[N];
int sm[N], lr[N];

signed main() {
    int n, p, q;
    cin >> n >> p >> q;

    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    if(p > n) p = n;
    if(q > n) q = n;

    int l = 1, r = 1e9, ans = 1e9;

    while(l <= r){
        int m = (l + r) / 2;
        for(int i = 0; i < n; i++){
            sm[i] = lower_bound(a, a + n, a[i] + m) - a;
            lr[i] = lower_bound(a, a + n, a[i] + 2 * m) - a;
        }
        sm[n] = lr[n] = n;
        for(int i = 0; i <= p; i++){
            for(int j = 0; j <= n; j++){
                dp[i][j] = 1e9;
            }
        }
        dp[0][0] = 0;
        for(int i = 0; i <= p; i++){
            for(int j = 0; j <= n; j++){
                if(dp[i][j] > q) continue;
                if(i < p){
                    int nxt = sm[j];
                    dp[i+1][nxt] = min(dp[i+1][nxt], dp[i][j]);
                }
                if(j < n and dp[i][j] < q){
                    int nxt = lr[j];
                    dp[i][nxt] = min(dp[i][nxt], dp[i][j] + 1);
                }
            }
        }

        bool ok = false;
        for(int i = 0; i <= p; i++){
            if(dp[i][n] <= q) ok = true;
        }

        if(ok) ans = m, r = m - 1;
        else l = m + 1;
    }

    cout << ans << endl;
}

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