oj.uz

답안 #888967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888967 2023-12-18T13:29:04 Z dwuy 구경하기 (JOI13_watching) C++14
100 / 100
 211 ms 32084 KB 
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 2005;

int n, p, q;
int a[MX];
int dp[MX][MX];
/// dp[i][j] : least large camera to check a[1, i], used j small camera;

void nhap(){
    cin >> n >> p >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    if(p+q>=n){
        cout << 1;
        exit(0);
    }
    sort(a+1, a+1+n);
}

bool ok(int mid){
    memset(dp, 0x3f, sizeof dp);
    memset(dp[0], 0, sizeof dp[0]);
    for(int i=1, sm=1, bg=1; i<=n; i++){
        while(a[i] - a[sm] + 1 > mid) sm++;
        while(a[i] - a[bg] + 1 > mid+mid) bg++;
        for(int j=0; j<=p; j++){
            dp[i][j] = min({dp[i][j], (j? dp[sm-1][j-1] : INF), dp[bg-1][j] + 1});
        }
    }
    return dp[n][p] <= q;
}

void solve(){
    int res = 0;
    for(int lo=1, hi=1000000000; lo<=hi;){
        int mid = (lo+hi)>>1;
        if(ok(mid)) res = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    cout << res;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 31836 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 65 ms 31912 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 66 ms 31832 KB Output is correct
8 Correct 63 ms 31912 KB Output is correct
9 Correct 66 ms 31836 KB Output is correct
10 Correct 63 ms 31836 KB Output is correct
11 Correct 66 ms 31836 KB Output is correct
12 Correct 67 ms 31836 KB Output is correct
13 Correct 67 ms 31832 KB Output is correct
14 Correct 63 ms 31916 KB Output is correct
15 Correct 64 ms 31916 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 31920 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 70 ms 31836 KB Output is correct
8 Correct 80 ms 31936 KB Output is correct
9 Correct 132 ms 32084 KB Output is correct
10 Correct 211 ms 31936 KB Output is correct
11 Correct 75 ms 31832 KB Output is correct
12 Correct 149 ms 31836 KB Output is correct
13 Correct 67 ms 31936 KB Output is correct
14 Correct 73 ms 31940 KB Output is correct
15 Correct 70 ms 31944 KB Output is correct