제출 #468447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468447		sumit_kk10	Watching (JOI13_watching)	C++14	100 / 100	592 ms	16220 KiB

watching

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 2e3 + 5;
const int MOD = 1e9 + 7;
int n, p, q, a[N], dp[N][N], top[N], toq[N];

int go(int i, int small, ll mid){
    if(small > p) return INT_MAX;
    if(i == n + 1) return 0;
    if(dp[i][small] != -1)
        return dp[i][small];
    int req = INT_MAX;
    req = min(req, go(top[i], small + 1, mid));
    req = min(req, go(toq[i], small, mid) + 1);
    return dp[i][small] = req;
}

bool check(ll mid){
    // let dp[i][j] denote the min no. of large cameras needed when we place atmost j small cameras
    // in the prefix of i.
    memset(dp, -1, sizeof dp);
    for(int i = 1; i <= n; ++i){
        int low = i + 1, high = n, res = n + 1;
        while(low <= high){
            int mid1 = (low + high) / 2;
            if(a[mid1] > a[i] + mid - 1){
                res = mid1;
                high = mid1 - 1;
            }
            else
                low = mid1 + 1;
        }
        top[i] = res;
        low = i + 1, high = n, res = n + 1;
        while(low <= high){
            int mid1 = (low + high) / 2;
            if(a[mid1] > a[i] + 2*mid - 1){
                res = mid1;
                high = mid1 - 1;
            }
            else
                low = mid1 + 1;
        }
        toq[i] = res;
    }
    return (go(1, 0, mid) <= q);
}

void solve(){
    cin >> n >> p >> q;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    if(p + q >= n){
        cout << "1\n";
        return;
    }
    sort(a + 1, a + n + 1);
    ll low = 1, high = 1e12, ans;
    while(low <= high){
        ll mid = low + (high - low) / 2;
        if(check(mid)){
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    cout << ans << "\n";
}

int main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

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