Submission #156766

#	Time	Username	Problem	Language	Result	Execution time	Memory
156766		brcode	Safety (NOI18_safety)	C++14	0 / 100	675 ms	205924 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[MAXN][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<=h;j++){
            int hold = dp[i-1][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][j] = d1.front().first+abs(j-arr[i]);
            if(j<=10){
             //   cout<<i<<" "<<j<<" "<<dp[i][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][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=1;i<MAXK;i++){
        ans = min(ans,dp[n][i]);
    }
    cout<<ans<<endl;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 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