Submission #143934

#TimeUsernameProblemLanguageResultExecution timeMemory
143934WhipppedCreamWatching (JOI13_watching)C++17
50 / 100
1041 ms16308 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; int n; const int maxn = 2005; int arr[maxn]; int dp[maxn][maxn]; int w; int solve(int p, int q) { if(dp[p][q] != -1) return dp[p][q]; int ans = 0; if(p> 0) { int lst = solve(p-1, q); if(lst == n) { return dp[p][q] = n; } int rng = arr[lst+1]+w-1; int val = upper_bound(arr+1, arr+n+1, rng)-arr-1; ans = max(ans, val); } if(q> 0) { int lst = solve(p, q-1); if(lst == n) { return dp[p][q] = n; } int rng = arr[lst+1]+2*w-1; int val = upper_bound(arr+1, arr+n+1, rng)-arr-1; ans = max(ans, val); } return dp[p][q] = ans; } int main() { int p, q; scanf("%d %d %d", &n, &p, &q); for(int i = 1; i<= n; i++) scanf("%d", &arr[i]); sort(arr+1, arr+n+1); n = unique(arr+1, arr+n+1)-(arr+1); if(p+q>= n) { printf("1\n"); return 0; } int lo = 1, hi = arr[n]-arr[1]+1; while(lo< hi) { int mid = (lo+hi)/2; memset(dp, -1, sizeof dp); w = mid; if(solve(p, q) == n) hi = mid; else lo = mid+1; } printf("%d\n", lo); }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:53:7: 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:54:34: 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", &arr[i]);
                             ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...