Submission #1207590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207590		mareksb	Watching (JOI13_watching)	C++20	50 / 100	358 ms	40112 KiB

watching

#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2,bmi,bmi2,popcnt,lzcnt")
#define fi first
#define se second
using namespace std;
const int N=2005;
const int CNT=2005;
int64_t a[N];
int dp[N][N];
int n,p,q;
bool check(int64_t w){
    dp[0][0]=0;
    for(int i=0;i<p;i++){
        for(int j=0;j<=q;j++){
            //if(dp[i][j]==n||(j>0&&dp[i+1][j-1]==n))continue;
            int64_t start=dp[i][j];
            int s=0;
            while(start+s<n&&a[start+s]-a[start]+1<=w){
                s++;
            }
            if(j==0){
                dp[i+1][j]=dp[i][j]+s;
                //cout<<"check0:"<<i+1<<' '<<j<<' '<<dp[i+1][j]<<'\n';
                continue;
            }
            start=dp[i+1][j-1];
            int l=0;
            while(start+l<n&&a[start+l]-a[start]+1<=2*w){
                l++;
            }

            dp[i+1][j]=max(dp[i][j]+s,dp[i+1][j-1]+l);
            //cout<<"check1:"<<i+1<<' '<<j<<' '<<dp[i+1][j]<<'\n';
        }
    }
    //cout<<dp[p][q]<<' '<<w<<'\n';
    return dp[p][q]==n;
}

void solve(){

    cin>>n>>p>>q;
    if(p+q>=n){
        cout<<1<<'\n';
        return;
    }
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    vector<int64_t> mids;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            mids.push_back(a[j]-a[i]+1);
            mids.push_back((a[j]-a[i]+2)/2);
        }
    }
    sort(mids.begin(),mids.end());
    mids.erase(unique(mids.begin(),mids.end()),mids.end());

    int64_t l=0;
    int64_t r=mids.size()-1;
    while(l<r){
        int64_t mid=(l+r)/2;
        bool c=check(mids[mid]);
        if(c){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    /*
    for(int i=0;i<mids.size();i++){
        cout<<mids[i]<<' ';
    }
    cout<<'\n';
    */
    cout<<mids[l]<<'\n';

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
    int64_t t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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