Submission #1012471

#TimeUsernameProblemLanguageResultExecution timeMemory
1012471Error404Watching (JOI13_watching)C++17
0 / 100
373 ms262144 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define f first #define s second #define vi vector<ll> #define pb push_back #define INF 100000000000 #define endl '\n' #define int ll int n,p,q; vi v; bool check(int k){ int dp[p+1][q+1]; memset(dp,0,sizeof(dp)); ll where; //cout << "K: " << k <<endl; for(int i = 0; i<= p; i++){ for(int j =0 ; j<= q;j++){ if(i==0 && j==0) dp[i][j] =1; else if(i==0){ where = dp[i][j-1]; dp[i][j] = upper_bound(v.begin(), v.end(), v[where]+k*2-1) - v.begin(); // cout <<i << " " <<j << " " << dp[i][j]<<endl; } else if(j==0){ where = dp[i-1][j]; dp[i][j] = upper_bound(v.begin(), v.end(), v[where]+k-1) - v.begin(); // cout <<i << " " <<j << " " << dp[i][j]<<endl; } else { where = dp[i-1][j]; dp[i][j] = upper_bound(v.begin(), v.end(), v[where]+k-1) - v.begin(); where = dp[i][j-1]; int hold = (upper_bound(v.begin(), v.end(), v[where]+k*2-1) - v.begin()); dp[i][j] = max(dp[i][j],hold); // cout <<i << " " <<j << " " << dp[i][j]<<endl; } if(dp[i][j]==n+1){ return true; } } } return false; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> p >> q; ll l = 1, r= INT_MAX; v.resize(n+1); v[0]=-INF; for(int i =1; i <= n; i++){ cin >> v[i]; } sort(v.begin(),v.end()); ll ans = 0; while(l<=r){ int m = (l+r)/2; // cout <<"RES: " <<m << " "<<check(m)<<endl; if(check(m)){ ans = m; r = m-1; } else l= m+1; } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...