Submission #1177241

#TimeUsernameProblemLanguageResultExecution timeMemory
1177241ASN49KSparklers (JOI17_sparklers)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> #define all(x) x.begin(),x.end() const int inf=1e9; using i64 = long long; const i64 INF=1e18; #define int long long const int N_MAX=100'000; int a[N_MAX],n,k,t; [[gnu::optimize("O3")]][[gnu::target("avx2")]] bool test(int s) { std::vector<int>xx(n); for(int i=0;i<n;i++) { xx[i]=a[i]-2*s*t*i; } int l=k,r=k,best_l=xx[k],best_r=xx[k]; bool modify=true; while(modify) { modify=false; while(l>0 && xx[l-1]>=best_r) { best_l=std::max(best_l , xx[--l]); modify=true; } while(r+1<n && xx[r+1]<=best_l) { best_r=std::min(best_r , xx[++r]); modify=true; } } //std::cout<<min[1][2]<<' '<<max[1][2]<<'\n'; return l==0 && r==n-1; } main() { std::cin>>n>>k>>t; k--; for(int i=0;i<n;i++) { std::cin>>a[i]; } //std::cout<<test(100); //return 0; int st=0,dr=a[n-1],rez=-1; while(st<=dr) { int mid=(st+dr)/2; if(test(mid)) { dr=mid-1; rez=mid; } else { st=mid+1; } } assert(rez!=-1); std::cout<<rez; return 0; } /* 2 1 10 200 300 */

Compilation message (stderr)

sparklers.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...