#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
using lint = long long;
using pi = pair<int, int>;
int n, k, a[MAXN];
int t;
bool solve(vector<lint> x, vector<lint> y){
if(x[0] < y[0]) return 0;
vector<int> sx = {0}, sy = {0};
for(int i=1; i<x.size(); i++){
if(x[sx.back()] <= x[i]) sx.push_back(i);
}
for(int i=1; i<y.size(); i++){
if(y[sy.back()] >= y[i]) sy.push_back(i);
}
vector<lint> prec;
for(int i=0; i+1<sy.size(); i++){
prec.push_back(*max_element(y.begin() + sy[i] + 1, y.begin() + sy[i + 1] + 1));
}
int cs = 0, ce = 0;
for(int i=0; i<sx.size(); i++){
while(ce + 1 < sy.size()){
lint nxtmax = prec[ce];
if(nxtmax <= x[sx[i]]) ce++;
else break;
}
if(i + 1 < sx.size()){
lint nxtmin = *min_element(x.begin() + sx[i] + 1, x.begin() + sx[i + 1] + 1);
while(cs <= ce && y[sy[cs]] > nxtmin) cs++;
if(cs > ce) return 0;
}
}
return ce + 1 == sy.size();
}
bool trial(int s){
lint L = min(2ll * t * s, 2ll * a[n]);
vector<lint> vu, vd;
for(int i=1; i<=n; i++){
if(i <= k) vu.push_back(a[i] - L * i);
if(i >= k) vd.push_back(a[i] - L * i);
}
reverse(vu.begin(), vu.end());
int mx1 = max_element(vu.begin(), vu.end()) - vu.begin();
int mx2 = min_element(vd.begin(), vd.end()) - vd.begin();
vector<lint> u1, u2, d1, d2;
for(int i=0; i<=mx1; i++) u1.push_back(vu[i]);
for(int i=0; i<=mx2; i++) d1.push_back(vd[i]);
for(int i=mx1; i<vu.size(); i++) u2.push_back(vu[i]);
for(int i=mx2; i<vd.size(); i++) d2.push_back(vd[i]);
reverse(u2.begin(), u2.end());
reverse(d2.begin(), d2.end());
return solve(u1, d1) && solve(u2, d2);
}
int main(){
scanf("%d %d %d",&n,&k,&t);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
int s = 0, e = 1e9;
while(s != e){
int m = (s+e)/2;
if(trial(m)) e = m;
else s = m + 1;
}
cout << s << endl;
}
Compilation message
sparklers.cpp: In function 'bool solve(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<x.size(); i++){
~^~~~~~~~~
sparklers.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<y.size(); i++){
~^~~~~~~~~
sparklers.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<sy.size(); i++){
~~~^~~~~~~~~~
sparklers.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<sx.size(); i++){
~^~~~~~~~~~
sparklers.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ce + 1 < sy.size()){
~~~~~~~^~~~~~~~~~~
sparklers.cpp:30:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + 1 < sx.size()){
~~~~~~^~~~~~~~~~~
sparklers.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return ce + 1 == sy.size();
~~~~~~~^~~~~~~~~~~~
sparklers.cpp: In function 'bool trial(int)':
sparklers.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=mx1; i<vu.size(); i++) u2.push_back(vu[i]);
~^~~~~~~~~~
sparklers.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=mx2; i<vd.size(); i++) d2.push_back(vd[i]);
~^~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&k,&t);
~~~~~^~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:61:31: 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",&a[i]);
~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
252 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
2 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
348 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
252 KB |
Output is correct |
| 21 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
252 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
2 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
348 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
252 KB |
Output is correct |
| 21 |
Correct |
2 ms |
256 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
| 23 |
Correct |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
376 KB |
Output is correct |
| 25 |
Correct |
3 ms |
376 KB |
Output is correct |
| 26 |
Correct |
3 ms |
376 KB |
Output is correct |
| 27 |
Correct |
3 ms |
376 KB |
Output is correct |
| 28 |
Correct |
3 ms |
376 KB |
Output is correct |
| 29 |
Correct |
3 ms |
376 KB |
Output is correct |
| 30 |
Correct |
3 ms |
376 KB |
Output is correct |
| 31 |
Correct |
3 ms |
376 KB |
Output is correct |
| 32 |
Correct |
3 ms |
376 KB |
Output is correct |
| 33 |
Correct |
3 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
376 KB |
Output is correct |
| 35 |
Correct |
3 ms |
380 KB |
Output is correct |
| 36 |
Correct |
3 ms |
376 KB |
Output is correct |
| 37 |
Correct |
3 ms |
404 KB |
Output is correct |
| 38 |
Correct |
3 ms |
376 KB |
Output is correct |
| 39 |
Correct |
3 ms |
380 KB |
Output is correct |
| 40 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
252 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
2 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
348 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
252 KB |
Output is correct |
| 21 |
Correct |
2 ms |
256 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
| 23 |
Correct |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
376 KB |
Output is correct |
| 25 |
Correct |
3 ms |
376 KB |
Output is correct |
| 26 |
Correct |
3 ms |
376 KB |
Output is correct |
| 27 |
Correct |
3 ms |
376 KB |
Output is correct |
| 28 |
Correct |
3 ms |
376 KB |
Output is correct |
| 29 |
Correct |
3 ms |
376 KB |
Output is correct |
| 30 |
Correct |
3 ms |
376 KB |
Output is correct |
| 31 |
Correct |
3 ms |
376 KB |
Output is correct |
| 32 |
Correct |
3 ms |
376 KB |
Output is correct |
| 33 |
Correct |
3 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
376 KB |
Output is correct |
| 35 |
Correct |
3 ms |
380 KB |
Output is correct |
| 36 |
Correct |
3 ms |
376 KB |
Output is correct |
| 37 |
Correct |
3 ms |
404 KB |
Output is correct |
| 38 |
Correct |
3 ms |
376 KB |
Output is correct |
| 39 |
Correct |
3 ms |
380 KB |
Output is correct |
| 40 |
Correct |
3 ms |
376 KB |
Output is correct |
| 41 |
Correct |
87 ms |
2800 KB |
Output is correct |
| 42 |
Correct |
5 ms |
656 KB |
Output is correct |
| 43 |
Correct |
26 ms |
1328 KB |
Output is correct |
| 44 |
Correct |
146 ms |
6628 KB |
Output is correct |
| 45 |
Correct |
133 ms |
5400 KB |
Output is correct |
| 46 |
Correct |
157 ms |
6600 KB |
Output is correct |
| 47 |
Correct |
172 ms |
6516 KB |
Output is correct |
| 48 |
Correct |
156 ms |
5576 KB |
Output is correct |
| 49 |
Correct |
150 ms |
6536 KB |
Output is correct |
| 50 |
Correct |
135 ms |
5488 KB |
Output is correct |
| 51 |
Correct |
161 ms |
6688 KB |
Output is correct |
| 52 |
Correct |
144 ms |
5416 KB |
Output is correct |
| 53 |
Correct |
152 ms |
6608 KB |
Output is correct |
| 54 |
Correct |
150 ms |
5340 KB |
Output is correct |
| 55 |
Correct |
139 ms |
5372 KB |
Output is correct |
| 56 |
Correct |
161 ms |
6792 KB |
Output is correct |
| 57 |
Correct |
135 ms |
5304 KB |
Output is correct |
| 58 |
Correct |
142 ms |
5500 KB |
Output is correct |
| 59 |
Correct |
140 ms |
4688 KB |
Output is correct |
| 60 |
Correct |
138 ms |
5616 KB |
Output is correct |
| 61 |
Correct |
145 ms |
5132 KB |
Output is correct |
| 62 |
Correct |
148 ms |
6804 KB |
Output is correct |
| 63 |
Correct |
144 ms |
5224 KB |
Output is correct |
| 64 |
Correct |
131 ms |
5460 KB |
Output is correct |
| 65 |
Correct |
128 ms |
5588 KB |
Output is correct |
| 66 |
Correct |
129 ms |
5328 KB |
Output is correct |
| 67 |
Correct |
126 ms |
5520 KB |
Output is correct |
| 68 |
Correct |
134 ms |
5392 KB |
Output is correct |
| 69 |
Correct |
138 ms |
5456 KB |
Output is correct |
