Submission #730440

#	Time	Username	Problem	Language	Result	Execution time	Memory
730440		Skywk	Safety (NOI18_safety)	C++11	100 / 100	52 ms	6296 KiB

safety

#include<bits/stdc++.h>
 
using namespace std;

class SlopeTrick{
private:
    priority_queue<long long> lft;
    priority_queue<long long, vector<long long>, greater<long long>> rgt;
    long long offset = 0;
public:
    long long min_value = 0;
    void insert(int x){
        if(lft.empty()){lft.push(x), rgt.push(x); return;}
        long long l_value = lft.top() - offset;
        long long r_value = rgt.top() + offset;
        if(x < l_value){
            lft.pop();
            lft.push(x + offset);
            lft.push(x + offset);
            rgt.push(l_value - offset);
            min_value += l_value - x;
        }
        else if(x > r_value){
            rgt.pop();
            rgt.push(x - offset);
            rgt.push(x - offset);
            lft.push(r_value + offset);
            min_value += x - r_value;
        }
        else{
            lft.push(x + offset);
            rgt.push(x - offset);
        }
    }
    void shift(int h){
        offset += h;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, h;
    cin>> N>> h;

    vector<int> a(N);
    for(int i=0; i<N; i++){
        cin>> a[i];
    }

    SlopeTrick st;
    for(int i=0; i<N; i++){
        st.insert(a[i]);
        st.shift(h);
    }
    cout<< st.min_value;
    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