Submission #478523

#	Time	Username	Problem	Language	Result	Execution time	Memory
478523		4ndrelus	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	185 ms	17912 KiB

bulves

#define DEBUG 0
#define TESTSETS 0
#if DEBUG
    #include <ultimate_power_2.h>
#else 
    #include <bits/stdc++.h>
    #define echo(...) {}
#endif
/* ------- utils ------- */
#define debug if(DEBUG)
#define P2(x) (1LL<<(x))
#define st first
#define nd second
#define mt make_tuple
#define gottagofast() ios::sync_with_stdio(0); cin.tie(0);
#define band(x, y) ((x) & (y))
#define bor(x, y) ((x) | (y))
#define all(x) (x).begin(), (x).end()
#define len(x) (int)(x).size()
#define ffor(i, a, b) for(int i = (a), i##e = (b); i <= i##e; i++)
#define dfor(i, a, b) for(int i = (a), i##e = (b); i >= i##e; i--)

#define forx(i, a, b) for(int i = (a), i##e = (b); i < i##e; i++) //!!! eXclusive
#define dforx(i, a, b) for(int i = (a), i##e = (b); i > i##e; i--)//!!! eXclusive

using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr LL INF = LLONG_MAX / 2 - 1;
constexpr int iINF = INT_MAX / 2 - 1;
LL MOD = 1'000'000'007;
int clamp(int x, int a, int b) { assert(a <= b); return min(max(x, a), b); }
template<class T> T sum(const vector<T>& vector) { return accumulate(vector.begin(), vector.end(), static_cast<T>(0)); }
template<class T> T max(const vector<T>& vector) { return *max_element(vector.begin(), vector.end()); }
template<class T> T min(const vector<T>& vector) { return *min_element(vector.begin(), vector.end()); }
template<class T> int popcnt(T x) { int c = 0; while (x > 0) c += x & 1, x >>= 1; return c; }
template<class T, class U> pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) { return { a.st + b.st, a.nd + b.nd }; }
vector<LL> factorize(LL x)
{
    assert(x > 0);
    vector<LL> f;
    while (x % 2 == 0)
        f.push_back(2),
        x /= 2;
    for (LL d = 3; d * d <= x; d += 2)
        while (x % d == 0)
            f.push_back(d),
            x /= d;
    if (x > 1)
        f.push_back(x);
    return f;
}
vector<pair<LL, int>> compress(vector<LL> v)
{
    vector<pair<LL, int>> p;
    sort(all(v));
    for (int i = 0, j; i < len(v); i = j) {
        for (j = i + 1; j < len(v) && v[i] == v[j]; j++);
        p.emplace_back(v[i], j - i);
    }
    return p;
}
int randx(int a, int b) { return rand() % (b-a) + a; }//rand exclusive [a, b)
LL fpow(LL a, LL b)
{
    if (b == 0) return 1;
    if (b % 2 == 1) return fpow(a, b - 1) * a % MOD;
    LL p = fpow(a, b / 2);
    return p * p % MOD;
}
LL iceil(LL a, LL b)
{
    assert(a > 0);
    return (a - 1) / b + 1;
}
/* --------------------- */

int n; 
vector<LL> a, b;

void Input()
{
    cin >> n; a = vector<LL>(n); b = vector<LL>(n);
    forx(i, 0, n)
        cin >> a[i] >> b[i];
}

void Solve()
{
    vector<LL> x(n+1, 0);
    forx(i, 0, n)
        x[i+1] = a[i] - b[i] + x[i];
    echo(x);
    /*auto x = a;
    forx(i, 0, n)x[i] -= i;
    x.insert(x.begin(), 0);*/
    

    LL adjust = 0;
    forx(i, 1, n+1) {
        if (x[i] < 0)
            adjust += -x[i],
            x[i] = 0;
     /*   else if (x[i] > x[n])
            adjust += x[i] - x[n],
            x[i] = a[n-1];*/
    }
    priority_queue<LL> pq; LL b = 0;
    forx(i, 1, n + 1) {
        pq.push(x[i]);
        pq.push(x[i]);
        b += pq.top() - x[i];
        pq.pop();
    }

    LL a = 0;
    while (x[n] < pq.top()) {
        a -= 1;
        b += pq.top();
        pq.pop();
    }
    
    cout << a*x[n]+b+adjust << "\n";
}

void Brute()
{
    
}

int main()
{
    gottagofast();
    int z = 1; 
    #if TESTSETS
        cin >> z; 
    #endif 
    forx(case_num, 0, z) {
        Input();
        echo(c::green, "---------------");
        Solve();
        echo(c::green, "---------------");
        Brute();
    }
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36