Submission #164933

#	Time	Username	Problem	Language	Result	Execution time	Memory
164933		gs18103	Safety (NOI18_safety)	C++14	35 / 100	398 ms	700 KiB

safety

#include <iostream>
#include <deque>
using namespace std;
const int MAXN = 5e3+5;
const int MAXK = 5e3+5;
deque<pair<int,int>> d1;
int dp[3][MAXK];
int arr[MAXN];
int main(){
    int n,h;
    cin>>n>>h;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=min(MAXK-1,h);j++){
            int hold = dp[(i-1)%2][j];
            while(d1.size() && d1.back().first>hold){
                d1.pop_back();
            }
            d1.push_back(make_pair(hold,j));
 
        }
        for(int j=0;j<MAXK;j++){
 
            dp[i%2][j] = d1.front().first+abs(j-arr[i]);
            if(j<=10){
              //  cout<<i<<" "<<j<<" "<<dp[i%2][j]<<" "<<d1.front().first<<" "<<d1.front().second<<endl;
            }
            if(d1.front().second == j-h){
                d1.pop_front();
            }
            if(j+1+h<MAXK){
                int hold = dp[(i-1)%2][j+1+h];
                while(d1.size() && d1.back().first>hold){
                    d1.pop_back();
                }
                d1.push_back(make_pair(hold,j+h+1));
            }
 
        }
        while(d1.size()){
            d1.pop_back();
        }
    }
    int ans = 1e9;
    for(int i=0;i<MAXK;i++){
        ans = min(ans,dp[n%2][i]);
    }
    cout<<ans<<endl;
}

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