Submission #299965

#TimeUsernameProblemLanguageResultExecution timeMemory
299965T0p_Watching (JOI13_watching)C++14
100 / 100
681 ms11776 KiB
#include<bits/stdc++.h> using namespace std; int n, p, q; long long arr[2020], dp[2020][2020]; int EndPoint(int s, long long w) { if(s > n) return n; int l = s, r = n; while(l != r) { int mid = (l+r+1)>>1; (arr[s] + w - 1 >= arr[mid]) ? l = mid : r = mid-1; } return l; } bool Test(long long w) { for(int i=1 ; i<=p ; i++) dp[i][0] = EndPoint(dp[i-1][0]+1, w); for(int i=1 ; i<=q ; i++) dp[0][i] = EndPoint(dp[0][i-1]+1, w+w); for(int i=1 ; i<=p ; i++) for(int j=1 ; j<=q ; j++) dp[i][j] = max(EndPoint(dp[i-1][j]+1, w), EndPoint(dp[i][j-1]+1, w+w)); return dp[p][q] == n; } int main() { scanf(" %d %d %d",&n,&p,&q); for(int i=1 ; i<=n ; i++) scanf(" %lld",&arr[i]); sort(arr+1, arr+n+1); if(p+q >= n) printf("1\n"); else { long long l = 1, r = 1e9; while(l != r) { long long mid = (l+r)>>1; (Test(mid)) ? r = mid : l = mid + 1; } printf("%lld\n",l); } return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf(" %d %d %d",&n,&p,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf(" %lld",&arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...