oj.uz

Submission #1093032

# Submission time Handle Problem Language Result Execution time Memory
1093032 2024-09-25T18:08:16 Z Seb Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 124 ms 11196 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T> //order_of_key = menores, find_by_order = consultar indexado en 0, regresa iterador
using ordered_set =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vii = vector<int>;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define mid ((l+r)>>1)
#define f first
#define s second
#define pb push_back
#define MP make_pair
#define all(x) (x).begin(),(x).end()
#define inicio(x) (*(x).begin())
#define rinicio(x) (*(x).rbegin())
#define SZ(x) (int)(x.size())

const ll MAXN = (ll)5e5 + 5;
const ll MOD = (ll)1e9 + 7;
const ll INF = (ll)1e12 + 5;
const ll OFFSET = (ll)1e6;

void tc() {
    priority_queue<ll> pq;
    ll N, a, b, sum = 0, brute = 0, ans = 0, M = 0, pre; cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b;
        a -= b;
        sum += a;
        brute += abs(sum);

        pq.push(max(sum, 0LL));
        pq.push(max(sum, 0LL));
        pq.pop();
    }
    cin >> a >> b;
    sum += a - b;

    pq.push(0);
    while (pq.top() > sum) {
        M--;
        pq.pop();
    }

    pre = pq.top();
    while (!pq.empty()) {
        ans -= M*abs(pre - pq.top());
        pre = pq.top();
        pq.pop();
        M--;
    }
    cout << brute - ans << "\n";
    return;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        tc();
    }
    return 0;
}

//checa tus constantes, n = 1? overflow?

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 13 ms 1248 KB Output is correct
5 Correct 23 ms 2264 KB Output is correct
6 Correct 78 ms 5716 KB Output is correct
7 Correct 102 ms 11196 KB Output is correct
8 Correct 124 ms 9144 KB Output is correct
9 Correct 94 ms 8644 KB Output is correct
10 Correct 93 ms 6336 KB Output is correct
11 Correct 83 ms 6336 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 13 ms 1248 KB Output is correct
5 Correct 23 ms 2264 KB Output is correct
6 Correct 78 ms 5716 KB Output is correct
7 Correct 102 ms 11196 KB Output is correct
8 Correct 124 ms 9144 KB Output is correct
9 Correct 94 ms 8644 KB Output is correct
10 Correct 93 ms 6336 KB Output is correct
11 Correct 83 ms 6336 KB Output is correct
12 Incorrect 32 ms 3028 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -