Submission #85511

#TimeUsernameProblemLanguageResultExecution timeMemory
85511nikolapesic2802Sparklers (JOI17_sparklers)C++14
100 / 100
36 ms1800 KiB
/* */ #include <bits/stdc++.h> #define ll long long #define pb push_back #define sz(x) (int)(x).size() #define mp make_pair #define f first #define s second #define all(x) x.begin(), x.end() using namespace std; int main() { int n,k,t; scanf("%i %i %i",&n,&k,&t); vector<int> arr(n+1); for(int i=1;i<=n;i++) { scanf("%i",&arr[i]); } int le=0,ri=1e9; while(le<ri) { int m=(le+ri)/2; vector<ll> X(n+1); for(int i=1;i<=n;i++) { X[i]=arr[i]-(ll)2*m*t*(i-1); } int l=k,r=k; ll minn=X[k],maxx=X[k]; int ok=1; while(ok) { ok=0; while(l>1&&X[l-1]>=minn) { ok=1; l--; maxx=max(maxx,X[l]); } while(r<n&&X[r+1]<=maxx) { ok=1; r++; minn=min(minn,X[r]); } } if(l==1&&r==n) { minn=1,maxx=n; if(X[minn]<X[maxx]) { le=m+1; continue; } maxx=X[1]; minn=X[n]; ok=1; while(ok) { ok=0; while(l<k&&X[l+1]>=minn) { ok=1; l++; maxx=max(maxx,X[l]); } while(r>k&&X[r-1]<=maxx) { ok=1; r--; minn=min(minn,X[r]); } } if(r==k&&l==k) { ri=m; } else { le=m+1; } } else { le=m+1; } } printf("%i\n",le); return 0; }

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i %i",&n,&k,&t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...