Submission #655150

#TimeUsernameProblemLanguageResultExecution timeMemory
655150hailWatching (JOI13_watching)C++17
50 / 100
1047 ms7764 KiB
#include <bits/stdc++.h> using namespace std; #define vi vector<int> #define vll vector<long long> #define pb push_back using ll= long long; #define fast_io ios::sync_with_stdio(0); cin.tie(0) #define inpint(x) int x; cin>>x #define inpll(x) long long x; cin>>x #define fl(i, n) for(int i=0; i<n; i++) #define flo(i, n) for(int i=1; i<=n; i++) #define int long long #define pi pair<int, int> #define mp make_pair #define ld long double const int MOD = 7 + (int)1e9; const int INF = (int)1e18; // int n, p, q; int a[2005]{}; bool check(int w) { int dp[p+1][q+1]{}; //p small q large for(int i=0; i<=p; i++) { for(int j=0; j<=q; j++) { //check p, q-1 and p-1, q if(j-1>=0) { int x = dp[i][j-1]; auto it = upper_bound(a+1, a+n+1, x); int y = *it; int z = y + (2*w) - 1; it = upper_bound(a+1, a+n+1, z); it--; int t = *it; dp[i][j] = max(dp[i][j], t); } if(i-1>=0) { int x = dp[i-1][j]; auto it = upper_bound(a+1, a+n+1, x); int y = *it; int z = y + (w) - 1; it = upper_bound(a+1, a+n+1, z); it--; int t = *it; dp[i][j] = max(dp[i][j], t); } if(dp[i][j]>=a[n]) return true; } } return false; } void solve() { cin>>n>>p>>q; for(int i=1; i<=n; i++) { cin>>a[i]; } sort(a+1, a+n+1); int low = 1; int high = INF; if(p+q>=n) { cout<<1; return; } while(high>low) { int mid = (high+low)/2; if(check(mid)) high = mid; else low = mid+1; } assert(high==low); cout<<high; } signed main() { fast_io; int t=1; //cin>>t; while(t--) { solve(); } cout<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...