Submission #211983

#	Time	Username	Problem	Language	Result	Execution time	Memory
211983		rdd6584	Safety (NOI18_safety)	C++14	100 / 100	75 ms	7072 KiB

safety

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = (ll)1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;


ll vec[200000];

int main() {
    int n;
    ll k;
    scanf("%d %lld", &n, &k);

    for (int i = 0; i < n; i++)
        scanf("%lld", &vec[i]);

    priority_queue<ll> upq;
    priority_queue<ll, vector<ll>, greater<ll>> dpq;

    upq.push(vec[0]);
    dpq.push(vec[0]);
    ll loff = 0;

    ll ans = 0;
    for (int i = 1; i < n; i++) {
        loff += -k;

        ll r = upq.top() + loff;
        ll t = dpq.top() - loff;

        if (r > vec[i]) {
            ans += r - vec[i];
            upq.pop();
            upq.push(vec[i] - loff);
            upq.push(vec[i] - loff);
            dpq.push(r + loff);
        }
        else if (t < vec[i]) {
            ans += vec[i] - t;
            dpq.pop();
            dpq.push(vec[i] + loff);
            dpq.push(vec[i] + loff);
            upq.push(t - loff);
        }
        else {
            upq.push(vec[i] - loff);
            dpq.push(vec[i] + loff);
        }
    }

    printf("%lld", ans);
}

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
safety.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &vec[i]);
         ~~~~~^~~~~~~~~~~~~~~~~

• 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