| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131507 |
2019-07-17T08:29:22 Z |
송준혁(#3182) |
Sparklers (JOI17_sparklers) |
C++14 |
|
2 ms |
376 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
int N, K;
LL A[101010];
LL P, ans;
priority_queue<pii> LPQ, RPQ;
LL LS, RS;
bool chk(LL k){
int l=K, r=K, ql=K, qr=K;
LS = RS = 0;
while (!LPQ.empty()) LPQ.pop();
while (!RPQ.empty()) RPQ.pop();
LPQ.push(pii(0, K));
k *= 2;
LL H=P*k;
while (!LPQ.empty() || !RPQ.empty()){
pii T;
if (LPQ.empty()) T = RPQ.top(), RPQ.pop();
else if (RPQ.empty()) T = LPQ.top(), LPQ.pop();
else {
if (LPQ.top().first - LS > RPQ.top().first - RS) T = LPQ.top(), LPQ.pop();
else T = RPQ.top(), RPQ.pop();
}
if (l <= T.second && T.second <= r && T.second != K) continue;
if (T.second > K){
LL x=0, y=0;
for (; r<T.second; r++){
y -= A[r+1]-A[r];
x = max(x, -y);
if (x > H) return false;
y += P*k;
}
T.first -= RS, H += T.first;
if (H < 0) return false;
RS += T.first;
}
if (T.second < K){
LL x=0, y=0;
for (; l>T.second; l--){
y -= A[l]-A[l-1];
x = max(x, -y);
if (x > H) return false;
y += P*k;
}
T.first -= LS, H += T.first;
if (H < 0) return false;
LS += T.first, l = T.second;
}
LL x=0, y=0;
for (int t=ql-1; t>0; t--){
y -= A[t+1]-A[t];
x = max(x, -y);
if (x > H) break;
y += P*k;
LPQ.push(pii(y+LS, t));
ql = t;
}
x=0, y=0;
for (int t=qr+1; t<=N; t++){
y -= A[t]-A[t-1];
x = max(x, -y);
if (x > H) break;
y += P*k;
RPQ.push(pii(y+RS, t));
qr = t;
}
}
if (l > 1 || r < N) return false;
return true;
}
int main(){
scanf("%d %d %lld", &N, &K, &P);
for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
if (A[1] == A[N]){
puts("0");
return 0;
}
LL L = 1, R = 1000000000;
while (L <= R){
LL mid = (L+R)/2;
if (chk(mid)) R = mid-1, ans = mid;
else L = mid+1;
}
printf("%lld\n", ans);
return 0;
}
Compilation message
sparklers.cpp: In function 'int main()':
sparklers.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld", &N, &K, &P);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:80:35: 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("%lld", &A[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
