Submission #730438

#	Time	Username	Problem	Language	Result	Execution time	Memory
730438		Skywk	Safety (NOI18_safety)	C++11	66 / 100	2049 ms	3248 KiB

safety

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

int h;

class SlopeTrick{
private:
    vector<long long> p;
    long long m = 0, b = 0;
    size_t N = 0;
    void insert_element(int &x){
        p.push_back(x);
        for(int i=N; i>0; i--){
            if(p[i] >= p[i-1]) break;
            swap(p[i], p[i-1]);
        }
        N++;
    }
public:
    void insert(int x){
        insert_element(x);
        insert_element(x);
        m++;
        b += -x;
    }
    void shift(){
        for(int i=0; i<N; i++){
            p[i] += (i < N/2 ? -h : h);
        }
        b -= (long long)h * (N >> 1);
    }
    long long get_min(){
        long long min_value = b;
        for(int i=N-1; i>=N/2; i--){
            min_value += p[i];
        }
        return min_value;
    }
};
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N;
    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();
    }
    cout<< st.get_min();
    return 0;
}

Compilation message (stderr)

safety.cpp: In member function 'void SlopeTrick::shift()':
safety.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i=0; i<N; i++){
      |                      ~^~
safety.cpp:29:24: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             p[i] += (i < N/2 ? -h : h);
      |                      ~~^~~~~
safety.cpp: In member function 'long long int SlopeTrick::get_min()':
safety.cpp:35:25: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int i=N-1; i>=N/2; i--){
      |                        ~^~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 0 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 0 / 29