Submission #1055252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055252		Mokocraft	Safety (NOI18_safety)	C++14	100 / 100	57 ms	7128 KiB

safety

#include <iostream>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <cmath>
#include <queue>
/*
void showq(std::priority_queue<int> qL, std::priority_queue<int, std::vector<int>, std::greater<int>> qR)
{
    while(!qL.empty())
    {
        std::cout << qL.top() << ' ';
        qL.pop();
    }
    while(!qR.empty())
    {
        std::cout << ' ' << qR.top();
        qR.pop();
    }
    std::cout << std::endl;
    return;
}
*/
int main()
{
    //freopen("duotaB.txt", "r", stdin);

    int n;
    long long h;
    std::cin >> n >> h;

    long long arr[n];
    for(int i = 0; i < n; i++)
        std::cin >> arr[i];

    std::priority_queue<long long> qL;
    std::priority_queue<long long, std::vector<long long>, std::greater<long long>> qR;

    long long min = 0;
    qL.emplace(arr[0]);
    qR.emplace(arr[0]);

    //showq(qL, qR);

    for(long long i = 1; i < n; i++)
    {
        if(arr[i] + (long long)i*h < qL.top())
        {
            qL.emplace(arr[i] + (long long)i*h);
            qL.emplace(arr[i] + (long long)i*h);
            min += qL.top() - arr[i] - (long long)i*h;
            qR.emplace(qL.top() - 2*(long long)i*h);
            qL.pop();
        }
        else if(arr[i] - (long long)i*h > qR.top())
        {
            qR.emplace(arr[i] - (long long)i*h);
            qR.emplace(arr[i] - (long long)i*h);
            min +=  arr[i] - (long long)i*h - qR.top();
            qL.emplace(qR.top() + (long long)2*(long long)i*h);
            qR.pop();
        }
        else
        {
            qL.emplace(arr[i] + (long long)i*h);
            qR.emplace(arr[i] - (long long)i*h);
        }
         

        //showq(qL, qR);
    }

    std::cout << min << std::endl;

    return 0;
}

• 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