Submission #799438

#	Time	Username	Problem	Language	Result	Execution time	Memory
799438		anton	Safety (NOI18_safety)	C++17	12 / 100	2083 ms	3960 KiB

safety

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


const int MAX_N = 2*1e5;
const int INF = 1e18;
int n, h, A[MAX_N], B[MAX_N], C[MAX_N];
int up_cost[MAX_N], down_cost[MAX_N];
int up_limit[MAX_N], down_limit[MAX_N];

void find_costs(int l, int r){
    for(int i = l; i<r; i++){
        C[i] = B[i]-A[i];
        if(C[i] == 0){
            up_cost[i] = 1;
            down_cost[i] = 1;
            up_limit[i]= INF;
            down_limit[i] = INF;
        }
        else if(C[i]<0){
            up_limit[i] = abs(C[i]);
            down_limit[i] =INF;
            up_cost[i] =-1;
            down_cost[i] =1;
        }
        else if(C[i]>0){
            up_limit[i] = INF;
            down_limit[i] = abs(C[i]);
            up_cost[i] =1;
            down_cost[i] =-1;
        }
    }
}
signed main(){
    cin>>n>>h;

    for(int i = 0; i<n; i++){
        cin>>A[i];
    }
    int res= 0;
    B[0] = A[0];
    C[0] =0;
    up_cost[0] = down_cost[0] = 1;
    for(int i = 1; i<n; i++){
        if(abs(A[i]-B[i-1])<=h){
            B[i] = A[i];
            C[i] = 0;
            up_cost[0] = down_cost[0] = 1;
        }
        else{
            bool has_zero = true;
            int prev_pos= -1;
            while(has_zero){
                has_zero = false;
                int pos = -1;
                int s= 0;
                if(A[i]>B[i-1]){
                    //cout<<"up"<<endl;
                    for(int j = i-1; j>prev_pos; j--){
                        s+=up_cost[j];
                        //cout<<"cost "<<up_cost[j]<<endl;
                        if(s==0){
                            pos = j;
                        }
                    }
                    //cout<<pos<<endl;
                    if(pos!=-1){
                        has_zero = true;
                        int lim = abs(B[i-1] -A[i]);
                        for(int j = pos; j<i; j++){
                            lim = min(lim, up_limit[j]);
                        }
                        if(pos>0){
                            lim = min(lim, B[pos-1]+h-B[pos]);
                        }
                        
                        //cout<<"lim "<<lim<<endl;

                        for(int j = pos; j<i; j++){
                            B[j]+=lim;
                        }
                        find_costs(pos, i);
                    }   

                }
                else{
                    //cout<<"down"<<endl;
                    for(int j = i-1; j>prev_pos; j--){
                        s+=down_cost[j];
                        
                        //cout<<"cost "<<down_cost[j]<<endl;
                        if(s==0){
                            pos = j;
                        }
                    }
                    if(pos!=-1){
                        //cout<<"pos "<<pos<<endl;
                        has_zero = true;

                        int lim = abs(B[i-1] -A[i]);
                        for(int j = pos; j<i; j++){
                            lim = min(lim, down_limit[j]);
                        }

                        if(pos>0){
                            lim = min(lim, abs(B[pos-1]-h-B[pos]));
                        }
                        //cout<<"lim "<<lim<<endl;

                        for(int j = pos; j<i; j++){
                            B[i]-=lim;
                        }
                        find_costs(pos, i);
                    }
                }

                prev_pos =pos;
            }

            if(abs(A[i]-B[i-1])<=h){
                B[i] = A[i];
                C[i] = 0;
                up_cost[0] = down_cost[0] = 1;
            }
            else{
                if(A[i]>B[i-1]){
                    B[i] = B[i-1] +h;
                }
                else{
                    B[i] = B[i-1] -h;
                }
                find_costs(i, i+1);
            }

            
            
        }
        find_costs(0, i+1);
        for(int i = 0; i<n; i++){
            //cout<<B[i]<<" ";
        }
        //cout<<endl;
    }

    find_costs(0, n);

    for(int i = 0; i<n; i++){
        res+=abs(C[i]);
    }

    for(int i = 0; i<n; i++){
        //cout<<B[i]<<" ";
    }
    //cout<<endl;

    cout<<res<<endl;


}

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