#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
int X[100000];
vplli L,R;
int main() {
int i;
int N,K,T;
scanf("%d %d %d",&N,&K,&T),K--;
for (i = 0; i < N; i++) scanf("%d",&X[i]);
int s = 0,e = 1e9;
while (s < e) {
int m = (s+e) / 2;
LLI ss2 = 0;
for (i = 1; i <= K; i++) {
LLI d = 2*m-(X[i]-X[i-1]);
ss2 += d;
if (d >= 0) L.pb(mp(d,0));
else {
LLI m = d;
while (!L.empty() && (L.back().first >= 0)) {
m = min(m,d+L.back().second);
d += L.back().first;
L.pop_back();
if (d >= 0) break;
}
L.pb(mp(d,m));
}
}
for (i = N-2; i >= K; i--) {
LLI d = 2*m-(X[i+1]-X[i]);
ss2 += d;
if (d >= 0) R.pb(mp(d,0));
else {
LLI m = d;
while (!R.empty() && (R.back().first >= 0)) {
m = min(m,d+R.back().second);
d += R.back().first;
R.pop_back();
if (d >= 0) break;
}
R.pb(mp(d,m));
}
}
reverse(L.begin(),L.end());
reverse(R.begin(),R.end());
int a = 0,b = 0;
LLI ss = 0;
int f = 0;
while ((a < L.size()) || (b < R.size())) {
if ((a < L.size()) && (L[a].first >= 0) && (ss+L[a].second >= 0)) ss += L[a].first,a++;
else if ((b < R.size()) && (R[b].first >= 0) && (ss+R[b].second >= 0)) ss += R[b].first,b++;
else {
f = 1;
break;
}
}
int good = 0;
if (f) {
if (ss2 < 0) good = 0;
else {
int aa = (int) L.size()-1,bb = (int) R.size()-1;
good = 1;
while ((aa >= a) && (bb >= b)) {
if ((aa >= a) && (L[aa].first <= 0) && (ss2-L[aa].first+L[aa].second >= 0)) ss2 -= L[aa].first,aa--;
else if ((bb >= b) && (R[bb].first <= 0) && (ss2-R[bb].first+R[bb].second >= 0)) ss2 -= R[bb].first,bb--;
else {
good = 0;
break;
}
}
}
}
else {
good = ((a == L.size()) && (b == R.size()) && (ss >= 0));
if (good) assert(ss == ss2);
}
if (good) e = m;
else s = m+1;
L.clear(),R.clear();
}
printf("%d\n",(s+T-1)/T);
return 0;
}
Compilation message
sparklers.cpp: In function 'int main()':
sparklers.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while ((a < L.size()) || (b < R.size())) {
| ~~^~~~~~~~~~
sparklers.cpp:106:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while ((a < L.size()) || (b < R.size())) {
| ~~^~~~~~~~~~
sparklers.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | if ((a < L.size()) && (L[a].first >= 0) && (ss+L[a].second >= 0)) ss += L[a].first,a++;
| ~~^~~~~~~~~~
sparklers.cpp:108:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | else if ((b < R.size()) && (R[b].first >= 0) && (ss+R[b].second >= 0)) ss += R[b].first,b++;
| ~~^~~~~~~~~~
sparklers.cpp:131:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | good = ((a == L.size()) && (b == R.size()) && (ss >= 0));
| ~~^~~~~~~~~~~
sparklers.cpp:131:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | good = ((a == L.size()) && (b == R.size()) && (ss >= 0));
| ~~^~~~~~~~~~~
sparklers.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
63 | scanf("%d %d %d",&N,&K,&T),K--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:64:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | for (i = 0; i < N; i++) scanf("%d",&X[i]);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
