#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 100010;
void print(vector<ll> &a) {
for(int i = 0; i < a.size(); i++) {
cout << a[i] << ' ';
}
cout << endl;
}
int N, K, T;
int X[MN];
bool check(int x) {
//cout << "check : " << x << endl;
vector<ll> le, ri;
for(int i = 0; i < K; i++) {
ll d = 1LL * T * x - (X[i + 1] - X[i]);
le.push_back(d);
}
reverse(le.begin(), le.end());
for(int i = K; i < N - 1; i++) {
ll d = 1LL * T * x - (X[i + 1] - X[i]);
ri.push_back(d);
}
//print(le);
//print(ri);
vector<ll> tmp;
ll sum = 0;
for(int i = 0; i < le.size(); i++) {
sum += le[i];
if(i == (int)le.size() - 1 || ((le[i] >= 0) ^ (le[i + 1] >= 0))) tmp.push_back(sum), sum = 0;
}
le = tmp;
tmp.clear();
sum = 0;
for(int i = 0; i < ri.size(); i++) {
sum += ri[i];
if(i == (int)ri.size() - 1 || ((ri[i] >= 0) ^ (ri[i + 1] >= 0))) tmp.push_back(sum), sum = 0;
}
ri = tmp;
//print(le);
//print(ri);
vector<pair<ll, ll> > L, R;
ll init = 0;
ll lim = 0;
ll neg = 0;
for(int i = (int)le.size() - 1; i >= 0; i--) {
if(le[i] >= 0) {
lim -= le[i];
neg -= le[i];
}
else {
lim = max(lim - le[i], -le[i]);
neg -= le[i];
}
if(neg > 0) {
L.push_back({ lim, neg });
lim = 0;
neg = 0;
}
}
init -= neg;
lim = 0;
neg = 0;
for(int i = (int)ri.size() - 1; i >= 0; i--) {
if(ri[i] >= 0) {
neg -= ri[i];
}
else {
lim = max(lim - ri[i], -ri[i]);
neg -= ri[i];
}
if(neg > 0) {
R.push_back({ lim, neg });
lim = 0;
neg = 0;
}
}
init -= neg;
//cout << init << endl;
reverse(L.begin(), L.end());
reverse(R.begin(), R.end());
/*
for(int i = 0; i < L.size(); i++) {
cout << "(" << L[i].first << ", " << L[i].second << ") ";
}
cout << endl;
for(int i = 0; i < R.size(); i++) {
cout << "(" << R[i].first << ", " << R[i].second << ") ";
}
cout << endl;
//*/
vector<ll> psum1(L.size());
vector<ll> psum2(R.size());
for(int i = 0; i < L.size(); i++) {
psum1[i] = L[i].second;
if(i) psum1[i] += psum1[i - 1];
}
for(int i = 0; i < R.size(); i++) {
psum2[i] = R[i].second;
if(i) psum2[i] += psum2[i - 1];
}
if(init < (psum1.size()? psum1.back() : 0) + (psum2.size()? psum2.back() : 0)) return false;
vector<int> pnt1(L.size());
vector<int> pnt2(R.size());
for(int i = 0; i < L.size(); i++) {
ll rem = i? init - psum1[i - 1] : init;
if(rem < L[i].first) return false;
rem -= L[i].first;
int s = 0, e = (int)psum2.size() - 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(psum2[m] <= rem) {
p = m;
s = m + 1;
}
else e = m - 1;
}
pnt1[i] = p;
}
for(int i = 0; i < R.size(); i++) {
ll rem = i? init - psum2[i - 1] : init;
if(rem < R[i].first) return false;
rem -= R[i].first;
int s = 0, e = (int)psum1.size() - 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(psum1[m] <= rem) {
p = m;
s = m + 1;
}
else e = m - 1;
}
pnt2[i] = p;
}
int pos = (int)R.size() - 1;
int mn1 = 1e9;
int mn2 = 1e9;
for(int i = (int)L.size() - 1; i >= 0; i--) {
mn1 = min(mn1, pnt1[i]);
while(pos >= 0 && pos > mn1) {
mn2 = min(mn2, pnt2[pos]);
pos--;
}
if(mn2 < i) return false;
}
return true;
}
int main() {
scanf("%d %d %d", &N, &K, &T);
K--;
for(int i = 0; i < N; i++) {
scanf("%d", &X[i]);
}
int s = 0, e = 1e9, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(check(2 * m)) {
p = m;
e = m - 1;
}
else s = m + 1;
}
printf("%d", p);
}
Compilation message
sparklers.cpp: In function 'void print(std::vector<long long int>&)':
sparklers.cpp:9:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < le.size(); i++) {
~~^~~~~~~~~~~
sparklers.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ri.size(); i++) {
~~^~~~~~~~~~~
sparklers.cpp:118:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < L.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp:122:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < R.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp:132:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < L.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < R.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:183:10: 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:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &X[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
