#include "bits/stdc++.h"
#define mxN 500005
#define bfS 1<<15
using namespace std;
long long pr[mxN];
int a[mxN];
inline namespace putin{
char buf[bfS];
int pos, len;
char nextChar(){
if (pos == len){
len = fread(buf, 1, bfS, stdin), pos = 0;
if (!len) return EOF;
}
return buf[pos ++];
}
int nextInt(){
int s = 1, x = 1;
char c;
while (!isdigit(c = nextChar()))
if ('-' == c) x = -1;
x *= c - '0';
while (isdigit(c = nextChar()))
x = x * 10 + c - '0';
return x;
}
}
inline namespace putout{
char buf[bfS];
char nmb[6];
int pos;
void flushOut(){
fwrite(buf, 1, pos, stdout);
pos = 0;
}
void writeChar(char c){
if (pos == bfS)
flushOut();
buf[pos ++] = c;
}
void writeInt(int x){
if (x < 0){
writeChar('-');
x *= -1;
}
int len = 0;
for (; x >= 10; x /= 10)
nmb[len ++] = '0' + x % 10;
writeChar('0' + x);
while (len)
writeChar(nmb[-- len]);
writeChar('\n');
}
void initOutput(){
assert(!atexit(flushOut));
}
}
int main(){
initOutput();
int N;
cin >> N;
for (int i = 1; i <= N; i ++)
a[i] = nextInt();
priority_queue<tuple<long long,int,int>> pq;
long long aux = 0;
int ans = 0;
pair<int,int> bs = {0, 0};
for (int i = 1; i <= N; i ++){
pr[i] = aux += a[i];
for(;;){
if (pq.empty()) break;
auto& [sm, cn, ix] = pq.top();
// sm = -sm;
if (-(aux - sm) <= 0){
bs = max(bs, {cn, ix});
pq.pop();
}
else break;
}
auto [cn, ix] = bs;
ans = cn + 1;
pq.emplace(pr[ix] - pr[i] - aux, cn + 1, i);
}
writeInt(ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |