Submission #1204817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204817		famafka	Safety (NOI18_safety)	C++20	18 / 100	113 ms	18724 KiB

safety

#include <iostream>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <vector>
#include <random>
#include <algorithm>
#include <climits>
#include <cmath>
#include <queue>
#include <iomanip>
#include <memory.h>
#include <cassert>

using namespace std;

const long long LINF = -1e18;

struct Slope
{
    multiset<long long> L, R;
    long long dl, dr;
    long long b;

    Slope()
    {
        dl = dr = b = 0;
    }

    void balance()
    {
        while (L.size() > R.size())
        {
            long long x = *L.rbegin() + dl;
            L.erase(--L.end());

            R.insert(x - dr);
        }
        while (R.size() > L.size())
        {
            long long x = *R.begin() + dr;
            R.erase(R.begin());

            L.insert(x - dl);
        }
    }

    void Expand(long long delta)
    {
        dl -= delta;
        dr += delta;

        b -= delta * L.size();
    }

    void addFirst(long long x)
    {
        b += x - LINF;

        L.insert(x);
        R.insert(x);
    }

    void add(long long x)
    {
        b += x - LINF;

        if (x <= *L.rbegin() + dl)
        {
            L.insert(x - dl);
            L.insert(x - dl);
        }
        else
        {
            R.insert(x - dr);
            R.insert(x - dr);
        }

        balance();
    }

    long long getMin()
    {
        long long prev = LINF;
        long long res = b;
        long long slope = -L.size();
        for (int x : L)
        {
            res += slope * (x + dl - prev);
            prev = x + dl;
            ++slope;
        }

        return res;
    }
};

int main()
{
    ios_base :: sync_with_stdio (false);
    cin.tie(NULL);

    #ifdef TESTMARKLOCAL
    freopen("in.txt", "r", stdin);
    #endif

    int n, h;
    cin >> n >> h;

    Slope res;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;

        if (i == 0)
            res.addFirst(x);
        else
        {
            res.Expand(h);
            res.add(x);
        }
    }

    cout << res.getMin() << '\n';

    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29