#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int v[200005];
struct slopetrick
{
int a,b;
priority_queue<int> *s;
slopetrick()
{
a = b = 0;
s = new priority_queue<int>;
}
void operator += (slopetrick other)
{
a += other.a;
b += other.b;
if(s->size()<other.s->size())
{
swap(s,other.s);
}
while(other.s->size())
{
s->push(other.s->top());
other.s->pop();
}
}
void elim()
{
while(a>0)
{
b += s->top();
s->pop();
--a;
}
}
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
v[i] = v[i-1] + a - b;
}
slopetrick rez;
int val = 0;
for(int i=1; i<n; i++)
{
slopetrick aux;
if(v[i]<0)
{
val += abs(v[i]);
aux.a = 1, aux.b = 0;
aux.s->push(0);
aux.s->push(0);
}
else if(v[i]>v[n])
{
val += v[i] - v[n];
aux.a = 1, aux.b = v[n];
aux.s->push(v[n]);
aux.s->push(v[n]);
}
else
{
aux.a = 1, aux.b = -v[i];
aux.s->push(v[i]);
aux.s->push(v[i]);
}
rez += aux;
rez.elim();
}
val += rez.b;
cout<<val<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
18 ms |
5244 KB |
Output is correct |
5 |
Correct |
29 ms |
10368 KB |
Output is correct |
6 |
Runtime error |
35 ms |
6456 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
18 ms |
5244 KB |
Output is correct |
5 |
Correct |
29 ms |
10368 KB |
Output is correct |
6 |
Runtime error |
35 ms |
6456 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |