Submission #999516

#	Time	Username	Problem	Language	Result	Execution time	Memory
999516		m0vlan	Watching (JOI13_watching)	C++17	0 / 100	1 ms	348 KiB

watching

#include <bits/stdc++.h>
using namespace std;
// author: Movlan
#define ll long long
#define vl __int128
#define int long long
#define br "\n"
#define sp " "
#define pb push_back
#define pf push_front
typedef pair<int,int> pii;
#define vi vector<int>;
#define vpii vector<pair<int,int>>
#define all(x) x.begin(),x.end()
#define IO ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
enum{
    INF=INT_MAX, MAXN = 2007
};
int n,p,q;
int a[MAXN];

bool check(int w){
    int i=0;
    int tp=p,tq=q,sum;
    while(i<n-1){
        sum=0;
        bool t=1;
        while(sum+(a[i+1]-a[i]+1)<=w && i<n-1 && tp>0){
            sum+=               (a[i+1]-a[i]+1);
            i++;
            t=0;
        }
        if(!t)tp--;
        sum=0;
        if(2*w<a[i+1]-a[i]+1 && tp!=0){tp--;i++;continue;}
        if(tq!=0){
            while (2 * w >= (a[i + 1] - a[i]+1) + sum && i < n - 1) {
                i++;
                sum += a[i + 1] - a[i];
            }
        }
        tq--;
        if(tp<=0 && tq<=0 && i<n-1)return false;
    }
    return true;
}


void solve(){
    cin>>n>>p>>q;
    set<int>s;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s.insert(a[i]);
    }
    n=s.size();
    int i=0;
    for(int v:s){
        a[i]=v;
        i++;
    }
    int w,l=0;int r=5*1e8,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid)){
            w=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<w;
}


signed main(){
    IO;
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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