Submission #468445

#	Time	Username	Problem	Language	Result	Execution time	Memory
468445		sumit_kk10	Watching (JOI13_watching)	C++14	50 / 100	1084 ms	16320 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];

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, 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;
    }
    req = min(req, go(res, small + 1, mid));
    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;
    }
    req = min(req, go(res, 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);
    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: 0 / 50