Submission #102095

#	Time	Username	Problem	Language	Result	Execution time	Memory
102095		win11905	Safety (NOI18_safety)	C++11	100 / 100	357 ms	19212 KiB

safety

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define iii tuple<int, int, int>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 2e5+5;

class safety {
private:
    int n;
    long k, high, now;
    multiset<long> Sl, Sr;
public:
    void solve(istream& cin, ostream& cout) {
        cin >> n >> k;
        for(int i = 0; i < n; ++i) {
            cin >> now;
            high += now;
            Sl.emplace(now + i*k), Sr.emplace(now - i*k);
            while(*Sl.rbegin() - i*k > *Sr.begin() + i*k) {
                long a = *Sl.rbegin(), b = *Sr.begin();
                Sl.erase(Sl.find(*Sl.rbegin())), Sr.erase(Sr.find(*Sr.begin()));
                Sl.emplace(b + 2*i*k), Sr.emplace(a - 2*i*k);
            }
            long pv = 0;
            while(!Sl.empty() && *Sl.begin() - i*k <= k) {
                high -= Sl.size() * (*Sl.begin() - i*k - pv);
                pv = *Sl.begin() - i*k;
                Sl.erase(Sl.begin());
            }
            high -= Sl.size() * (k - pv);
        }
        long pv = 0, ptr = Sl.size();
        for(auto x : Sl) {
            high -= ptr-- * (x - n*k - pv);
            pv = x - n*k;
        }
        cout << high << endl;
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        safety *obj = new safety();
        obj->solve(in, out);
    }
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    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