Submission #1327552

#TimeUsernameProblemLanguageResultExecution timeMemory
1327552nobasistakenWatching (JOI13_watching)C++20
50 / 100
32 ms2152 KiB
#include<bits/stdc++.h>
#include <set>
using namespace std;
#define int long long
//#define endl '\n'
bool testcases=0;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
const int MOD=1e18;
const int inf=1e18;
const int mynum=21;
const int N=100;
const int siz=N+mynum;
const int int32=4294967295;
bool dp[siz][siz][siz];
bool check(int w,int p,int q,int n,vector<int>& v){
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    vector<int> n1(n),n2(n);
    for(int i=0;i<n;i++){
        n1[i]=lower_bound(v.begin(),v.end(),v[i]+w)-v.begin();
        n2[i]=lower_bound(v.begin(),v.end(),v[i]+2*w)-v.begin();
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=p;j++){
            for(int h=0;h<=q;h++){
                if(!dp[i][j][h])continue;
                if(j<p){
                    dp[n1[i]][j+1][h]=1;
                }
                if(h<q){
                    dp[n2[i]][j][h+1]=1;
                }
            }
        }
    }
    int ans=0;
    for(int j=0;j<=p;j++){
        for(int h=0;h<=q;h++){
            ans|=dp[n][j][h];
        }
    }
    return ans;
    //cout<<ans;
}
int bs(int n,int p,int q,vector<int>& v){
    int l=1,r=1e9,mid,ans=1e9;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid,p,q,n,v)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}
void solve(){
    int n,p,q,w;
    cin>>n>>p>>q;
    vector<int> v(n);
    for(int& i:v)cin>>i;
    sort(v.begin(),v.end());
    p=min(p,n);
    q=min(q,n);
    cout<<bs(n,p,q,v);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    if(testcases)cin>>t;
    while(t--){
        solve();
    }
}

/*
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
------------------------------------------##+----------+##------------------------------------------
----------------------------------------+###------------###+----------------------------------------
--------------------------+###------------##------------##------------###+--------------------------
--------------------------+###+------#+#--##+--#+##+#---##--#+#-------###---------------------------
----------+---------------++-+###-----##++##+-+#-++-++-+##++##-----###+-++---------------+----------
----------+###+---------------####+##+#+##-#+--+#--#+--+#-##+####+####---------------+###+----------
---------#####+##++--------+++#######+---##++----+-----++##---+#######+++--------++##+#####---------
-----+#++##-######-##-------##++#####+----+##+--++----+##+----######++#+-------##-######-##++#+-----
--------#################-----+##+####---+++##--+++---##+++---####+##+-----#################--------
-------##---############-+++---####+##---++##---#++#---##++---##+####---+++-############---##-------
-------+-----##############+---######-+--+##+---##+#+--+##+--+-######---+##############-----#-------
-------+-##+--+#############+---+##++-#---#+----##+#+---+#---#-++##+---+#############+--+##-+-------
---------###---###+++#########---####-##-------+##+#+-------##-####---#########+++###---###---------
----------+###--+#######++######+--++-##+----+-###+##-+----+#+-++--+######++#######+--###+----------
----------+####---+###########++##++--+----+++####+###+-++------++##++###########+---####+----------
--------+##+####---+###############+--------###++++-+###--------+###############----####+##+--------
---------++###+##+--++---+++++++++++-#------+##-+##+-##+------#-+++++++++++----#--+##+###++---------
---------+-+#####+-+###############++-#+-----++-+###-++-----+#-+################+-+#####+-+---------
---------+#########+-+#----++++#######-##+---#+++##+++#---+##-#######++++----#+-+#########+---------
----------#++########+----#########+++#+--++####+#++#####+--+#+-+#########-----########++#----------
----------#---+#+######-----#+----+####-+++##+#+####+#+##+++-####+----+#-----######+#----++---------
---------#####-#####++#-#---------+++--######++#++++#+#######+++++---------#-#++#####-#####---------
----------++#####+-+###+##------+###+++#######+######+#######+++###+------##-###+-+#####++----------
----------++#--+#######++#------#++##+-+---#+##########+#+--+--##++#------##-#######+--#++----------
----------------#######+###----###+----------##########----------+###----###+#######----------------
----------------+#+####-###+---##-------------+###+##+--------+----##---+###-####+#+----------------
----------------+#-###+-+#+--+##---##+---++--##########--++---+##---##---+#+-+###-#+----------------
----------------+#--+###----+##---+#----###+-##########-+###----#+---##-----###+--#+----------------
----------------+#--+##----+##---+#+----+#--+##########---#+----+#+---##-----##---#+----------------
----------------+#---#-----##----#+-----+#--###########+--#+-----+#----##-----#---#+----------------
---------------------+----##+---##------#+--+##########+--+#------##---+##----+---------------------
---------------------+---##+---+#------+#-----########-----#+------#+---+##---+---------------------
---------------------+---##----#-------+#----+########+----#+-------#----##+--+---------------------
---------------------+---#----++-------+#-----########-----#+-------#+----#+--+---------------------
---------------------+---#----+---------#----+########-----#+-------++----+---+---------------------
---------------------+---#----+---------+-----########-----#+--------+----+---+---------------------
-------------------------#--------------+-----########-----+--------------#+------------------------
-------------------------+--------------+-----########-----+--------------+-------------------------
-------------------------#--------------------+#######--------------------#+------------------------
------------------------+#--------------------########--------------------#+------------------------
------------------+---#+##--------------------#######+--------------------##+#--++------------------
------------------###+####+#+--------------+#+#+####+++#+--------------+#+####+###------------------
-------------------##+####+#+-+#+----------###-+####+-###----------+#--+#+####+#+-------------------
--------------------########+##---------+##+-#--++#+--#-+##+--------+##+########--------------------
----------------+++++############+------+###--#------#--###+------+###########+++++-----------------
----------------+-----+-----++-+--+---+-+--##+##-+#-#++#+--+-#---+--+-++-----+-----+----------------
--------------------------------------+##+---###+##+###---+##+--------------------------------------
-----------------------------------------+###++#-+#-#+++##+-----------------------------------------
-------------------------------------------+++++-+#-++++--------------------------------------------
-------------------------------------++---+++++++++++++++++--++-------------------------------------
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------

\\\\\\
Machine
I will cut you down
break you apart
splay the gore of your profane form across the stars
I will grind you down until the very sparks cry for mercy
My hands shall relish
Ending you
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...