Submission #1207587

#TimeUsernameProblemLanguageResultExecution timeMemory
1207587mareksbWatching (JOI13_watching)C++20
0 / 100
447 ms43508 KiB
#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; 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; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...