Submission #1135451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135451		MunkhturErdenebat	Watching (JOI13_watching)	C++20	0 / 100	1 ms	580 KiB

watching

#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
#include <stdlib.h>
 #define ll long long
using namespace std;
    ll k[2001006],a,b,c,d,e,f,m,i,j,n,h,g,l,r,ka,p,q[200005];
    map<ll,ll> maa,mii,mee;
    vector<ll> vas[25],vis,vii;
    pair<ll,ll> jun,t[200005];
    string x;
int main(){
    cin>>a>>b>>c;
    for(i=0 ; i<a ; i++){
        cin>>k[i];
    }
    sort(k,k+a);
    if(b+c>=a){
        cout<<1;
        return 0;
    }
    for(i=0 ; i<a-1 ; i++){
        
        t[i].first=k[i+1]-k[i];
        t[i].second=k[i];
    }
    sort(t,t+a-1);
    for(i=a-b-c ; i<a-1 ; i++){
        maa[t[i].second]=1;
    }
    l=k[0];
    h=0;
    for(i=0 ; i<a ; i++){
        if(maa[k[i]]==1 || i==a-1){
            if(k[i]==k[i-1]){
                l=k[i+1];
                continue;
            }
            q[h]=k[i]-l+1;
            h++;
            l=k[i+1];
        }
    }
    
    sort(q,q+h);
    l=1;
    ka=h;
    r=1000000000;
    while(l<r){
        h=0;
        g=0;
        m=(l+r-1)/2;
        for(i=0 ; i<ka ; i++){
            h+=q[i]/(2*m);
        if(q[i]%(2*m)>m){
            h++;
        }
        else{
            if(q[i]%(2*m)!=0){
                g++;
            }
        }
        }
        if(h>c){
            g+=(h-c)*2;
            h=c;
            
        }
        if(h<c){
            g-=(c-h);
            h=c;
        }
        if(h<=c && g<=b){
            r=m;
        }
        else{
            l=m+1;
        }
        
    }
    cout<<l<<endl;
}

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