oj.uz

Submission #546130

# Submission time Handle Problem Language Result Execution time Memory
546130 2022-04-06T13:20:15 Z gimabd30 Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 108 ms 15212 KB 
//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;


#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define ll long long
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) -  begin(x))
#define ld long double
#define sz(s) (int) size(s)
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define mt make_tuple
#define int128 __int128


template<typename T>
bool ckmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmax(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}


int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const ll infL = 3e18;
const int infI = 1e9 + 7;
const int N = 500001;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;

ll A[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        A[i] = (i ? A[i - 1] : 0) + a - b;
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] < 0) {
            //it means that on our prefix sum(b) > sum(a) so we have to take some a's from right and put them here
            ans += -A[i];
            A[i] = 0;
        }
        if (A[i] > A[n - 1]) {
            //it means that now we have to take some from here and put them righter
            ans += A[i] - A[n - 1];
            A[i] = A[n - 1];
        }
    }
    //now everything on every prefix is alright so let's go to solve classic problem about making this array non-decreasing
    priority_queue<ll> pq;
    for (int i = 0; i < n; ++i) {
        pq.push(A[i]);
        pq.push(A[i]);
        pq.pop();
        ans += pq.top() - A[i];
    }
    cout << ans;
    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 1368 KB Output is correct
5 Correct 15 ms 2260 KB Output is correct
6 Correct 50 ms 4864 KB Output is correct
7 Correct 108 ms 15212 KB Output is correct
8 Correct 101 ms 13272 KB Output is correct
9 Correct 100 ms 12660 KB Output is correct
10 Correct 72 ms 10352 KB Output is correct
11 Correct 71 ms 10404 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 1368 KB Output is correct
5 Correct 15 ms 2260 KB Output is correct
6 Correct 50 ms 4864 KB Output is correct
7 Correct 108 ms 15212 KB Output is correct
8 Correct 101 ms 13272 KB Output is correct
9 Correct 100 ms 12660 KB Output is correct
10 Correct 72 ms 10352 KB Output is correct
11 Correct 71 ms 10404 KB Output is correct
12 Incorrect 30 ms 4100 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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 36.0

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