Submission #253892

#TimeUsernameProblemLanguageResultExecution timeMemory
253892ChrisTWatching (JOI13_watching)C++17
100 / 100
213 ms16248 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2005; typedef long long ll; typedef pair<int,int> pii; int dp[MAXN][MAXN], a[MAXN],p,q,n; int findlast (int cur, int w) { return max((int)(lower_bound(a+1,a+1+n,cur-w+1)-a-1),0); } bool check (int w) { memset(dp,0x3f,sizeof dp); memset(dp[0],0,sizeof dp[0]); for (int i = 1; i <= n; i++) { int lp = findlast(a[i],w), lq = findlast(a[i],w<<1); for (int j = 0; j <= p; j++) { dp[i][j] = dp[lq][j] + 1; if (j) dp[i][j] = min(dp[i][j],dp[lp][j-1]); } } return dp[n][p] <= q; } int main() { int ans=INT_MAX; scanf ("%d %d %d",&n,&p,&q); if (p + q >= n) return !printf ("1\n"); for (int i = 1; i <= n; i++) scanf ("%d",&a[i]); sort(a+1,a+1+n); for (int low = 1, high = 1e9,mid; low <= high;) { if (check(mid = (low + high)>>1)) high = mid-1, ans = mid; else low = mid+1; } printf ("%d\n",ans); return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:23:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d",&n,&p,&q);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~
watching.cpp:25:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; i++) scanf ("%d",&a[i]);
                                ~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...