Submission #499806

#	Time	Username	Problem	Language	Result	Execution time	Memory
499806		blue	Safety (NOI18_safety)	C++17	100 / 100	238 ms	20952 KiB

safety

#include <iostream>
#include <set>
#include <vector>
using namespace std;

using ll = long long;

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

    int N;
    ll H;
    cin >> N >> H;

    ll s0;
    cin >> s0;

    multiset<ll> left;
    ll left_lp = 0;

    multiset<ll> right;
    ll right_lp = 0;

    left.insert(s0);
    right.insert(s0);

    ll ans = 0;


    for(int i = 2; i <= N; i++)
    {
        ll S;
        cin >> S;

        left_lp -= H;
        right_lp += H;

        if(S <= left_lp + *left.rbegin())
        {
            ans += left_lp + *left.rbegin() - S;

            right.insert(-right_lp + *left.rbegin() + left_lp);
            left.erase(left.find(*left.rbegin()));
            left.insert(S - left_lp);
            left.insert(S - left_lp);
        }
        else if(S >= right_lp + *right.begin())
        {
            ans += S - (right_lp + *right.begin());

            left.insert(-left_lp + *right.begin() + right_lp);
            right.erase(right.find(*right.begin()));
            right.insert(S - right_lp);
            right.insert(S - right_lp);
        }
        else
        {
            left.insert(-left_lp + S);
            right.insert(-right_lp + S);
        }
    }

    cout << ans << '\n';
}

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