Submission #574519

#	Time	Username	Problem	Language	Result	Execution time	Memory
574519		timreizin	Safety (NOI18_safety)	C++17	100 / 100	51 ms	3640 KiB

safety

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <vector>
#include <bitset>
#include <string>
#include <algorithm>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <fstream>
#include <numeric>
#include <tuple>
#include <ctime>
#include <random>
#include <array>
#include <cassert>
#include <complex>
#include <valarray>
#include <set>
#include <chrono>

using namespace std;

#define sorti(a) sort((a).begin(), (a).end());
#define reversi(a) reverse((a).begin(), (a).end());
#define yes cout << "Yes\n";
#define no cout << "No\n";
#define ans(a) cout << a << '\n';
#define read(a, n) {(a).resize(n); for (auto &i : a) cin >> i;}
//#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const int INF = 2147483647;
const ll LONGINF = 9223372036854775807;
const ll MOD = 1e9 + 7;

void solve()
{
    int n;
    ll h;
    cin >> n >> h;
    ll res = 0;
    priority_queue<ll> pql;
    pql.push(-1e9);
    priority_queue<ll, vector<ll>, greater<>> pqr;
    for (int i = 0; i < n; ++i)
    {
        ll a;
        cin >> a;
        ll x = pql.top() - h * i;
        if (a == x)
        {
            pql.push(a + h * i);
            pqr.push(a - h * i);
        }
        else if (a > x)
        {
            pqr.push(a - h * i);
            pqr.push(a - h * i);
            ll x = pqr.top() + h * i;
            pqr.pop();
            pql.push(x + h * i);
            res += a - x;
        }
        else
        {
            pql.push(a + h * i);
            pql.push(a + h * i);
            ll x = pql.top() - h * i;
            pql.pop();
            pqr.push(x - h * i);
            res += x - a;
        }
    }
    ans(res)
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    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