oj.uz

Submission #799438

# Submission time Handle Problem Language Result Execution time Memory
799438 2023-07-31T14:22:53 Z anton Safety (NOI18_safety) C++17
12 / 100
 2000 ms 3960 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 308 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 3960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 1 ms 312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 1 ms 312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 1 ms 312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 1 ms 312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 1 ms 312 KB Output isn't correct
9 Halted 0 ms 0 KB -