Submission #1102171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102171		Icelast	Watching (JOI13_watching)	C++17	100 / 100	339 ms	16244 KiB

watching

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
};
void solve(){
    int n, P, Q;
    cin >> n >> P >> Q;
    P = min(P, n);
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a.begin()+1, a.end());
    vector<vector<int>> p(n+1, vector<int>(3));
    //minimum number of big camera need for prefix-i event, j small camera used
    vector<vector<int>> f(n+1, vector<int>(P+1));
    auto check = [&](ll x) -> bool{
        for(int i = 1; i <= n; i++){
            p[i][1] = lower_bound(a.begin()+1, a.end(), a[i]-x+1) - a.begin();
            p[i][2] = lower_bound(a.begin()+1, a.end(), a[i]-x*2+1) - a.begin();
        }
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= P; j++){
                f[i][j] = INF;
            }
        }
        f[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= P; j++){
                if(j > 0) f[i][j] = min(f[i][j], f[p[i][1]-1][j-1]);
                f[i][j] = min(f[i][j], f[p[i][2]-1][j]+1);
            }
        }
        int mn = INF;
        for(int j = 0; j <= P; j++){
            mn = min(mn, f[n][j]);
        }
        return mn <= Q;
    };
    ll l = 1, r = 1e9, mid;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid)){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << l;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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