Submission #51464

#TimeUsernameProblemLanguageResultExecution timeMemory
51464vovinamWatching (JOI13_watching)C++14
0 / 100
239 ms31808 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int a[2001], dp[2001][2001], posp[2001] , posq[2001], n , p , q; int check(int w) { memset(dp , - 1, sizeof(dp)); for(int i = 0 ; i < n ; ++i) { posp[i] = upper_bound(a,a + n,a[i] + w - 1) - a; posq[i] = upper_bound(a,a + n,a[i] + w << 1 - 1) - a; } dp[0][0] = 0; for(int i = 0 ; i <= p ; ++i) { for(int j = 0 ; j <= q ; ++j) { if(dp[i][j] >= 0) { if(dp[i][j] >= n) return 1; dp[i + 1][j] = max(dp[i + 1][j], posp[dp[i][j]]); dp[i][j + 1] = max(dp[i][j + 1], posq[dp[i][j]]); } } } return 0; } //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a //a signed main(){ cin >> n >> p >> q; for(int i = 0 ; i < n ; ++i) cin >> a[i]; sort(a, a + n); int l = 1, r = 1e9, mid = (l + r) >> 1; while(l != r) { if(check(mid) == 1) r = mid; else l = mid + 1; mid = (l + r) >> 1; } cout << l; }

Compilation message (stderr)

watching.cpp: In function 'long long int check(long long int)':
watching.cpp:11:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   posq[i] = upper_bound(a,a + n,a[i] +  w << 1 - 1) - a;
                                 ~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...