Submission #1134104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134104		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 fr first
#define sc second
 #define ll long long
using namespace std;
    ll a,b,c,d,e,f,m[500005],i,j,n,h,g,l,r,ka,p,q,k[2005],t[2005];
    map<ll,ll> maa,mii,mee;
    vector<ll> vis,vo,vi;
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=1 ; i<a ; i++){
        t[i]=k[i]-k[i-1]+1;
    }
    sort(t+1,t+a);
    for(i=a-1 ; i>a-1-(b+c-1) ; i--){
        maa[t[i]]++;
    }
    l=1;
    r=1000000000;
    g=k[0];
    p=0;
    for(i=1 ; i<a ; i++){
        if(i==a-1){
            m[p]=k[i]-g+1;
            p++;
            maa[k[i]-k[i-1]+1]--;
            break;
        }
        if(maa[k[i]-k[i-1]+1]>0 ){
            m[p]=k[i-1]-g+1;
            p++;
            maa[k[i]-k[i-1]+1]--;
            g=k[i];
        }
        
    }
    while(l<r){
        n=(l+r-1)/2;
        g=0;
        h=0;
        for(i=0 ; i<p ; i++){
            
            g+=m[i]/(2*n);
            h+=((m[i]%(2*n))+n-1)/n;
            if(((m[i]%(2*n))+n-1)/n>1){
                g++;
                h-=2;
            }
        }
        if(g>c){
            h+=(g-c)*2;
        }
        else{
            h-=(c-g);
        }
        g=c;
        if(h<=b && g<=c){
            r=n;
        }
        else{
            l=n+1;
        }
    }
    cout<<l;
}

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