Submission #445554

#TimeUsernameProblemLanguageResultExecution timeMemory
445554julian33Watching (JOI13_watching)C++14
100 / 100
271 ms16196 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=2e3+5; //make sure this is right const int mod=1e9+7; int dp[mxN][mxN],a[mxN],n,p,q; bool check(int k){ memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++){ int go=lower_bound(a,a+1+n,a[i]-k+1)-a; int go2=lower_bound(a,a+1+n,a[i]-2*k+1)-a; if(go) go--; if(go2) go2--; for(int j=1;j<=p;j++){ if(dp[go][j-1]!=-1) dp[i][j]=dp[i][j]==-1?dp[go][j-1]:min(dp[i][j],dp[go][j-1]); if(dp[go2][j]!=-1 && dp[go2][j]<q) dp[i][j]=dp[i][j]==-1?dp[go2][j]+1:min(dp[i][j],dp[go2][j]+1); } if(dp[go2][0]!=-1 && dp[go2][0]<q) dp[i][0]=dp[i][0]==-1?dp[go2][0]+1:min(dp[i][0],dp[go2][0]+1); } for(int i=0;i<=p;i++){ if(dp[n][i]!=-1) return 1; } return 0; } int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif cin>>n>>p>>q; mina(p,n); mina(q,n); for(int i=1;i<=n;i++) cin>>a[i]; sort(a,a+1+n); int l=1; int r=1e9; int ans=1e9; while(l<=r){ int mid=(l+r)>>1; if(check(mid)){ ans=mid; r=mid-1; } else{ l=mid+1; } } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...