Submission #942084

#TimeUsernameProblemLanguageResultExecution timeMemory
942084dshfjkaWatching (JOI13_watching)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #define LL long long using namespace std; int main() { LL n,p,q; scanf("%lld %lld %lld",&n,&p,&q); LL arr[n+5]; for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]); sort(arr+1,arr+n+1); LL left=1,right=10,ans=-1; q=min(q,n); p=min(p,n); LL all=p+q; while(left<=right) { LL mid=(left+right)/2; // printf("mid=%lld\n",mid); LL dp[n+5][p+5]; // now, p , minimum q for(LL a=0;a<=n+1;a++)for(LL b=0;b<=p;b++)dp[a][b]=1e9; LL lastp=1,lastq=1; dp[1][0]=0; for(LL a=1;a<=n;a++) { while(lastp!=n+1 && arr[lastp]-arr[a]+1<=mid)lastp++; while(lastq!=n+1 && arr[lastq]-arr[a]+1<=2*mid)lastq++; for(LL b=p;b>=0;b--) { if(dp[a][b]>=2500)continue; if(b!=p)dp[lastp][b+1]=min(dp[lastp][b+1],dp[a][b]); dp[lastq][b]=min(dp[lastq][b],dp[a][b]+1); // printf("dp[%lld][%lld] = %lld\n",lastp,b+1,dp[lastp][b+1]); // printf("dp[%lld][%lld] = %lld\n",lastq,b,dp[lastq][b]); } } bool bisa=false; for(LL b=0;b<=p;b++) { if(dp[n+1][b]<=q){ bisa=1; break; } } if(bisa){ ans=mid; right=mid-1; } else left=mid+1; } printf("%lld\n",ans); }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:14:5: warning: unused variable 'all' [-Wunused-variable]
   14 |  LL all=p+q;
      |     ^~~
watching.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  scanf("%lld %lld %lld",&n,&p,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:9:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
      |                      ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...