Submission #830702

#	Time	Username	Problem	Language	Result	Execution time	Memory
830702		vjudge1	Safety (NOI18_safety)	C++17	4 / 100	504 ms	262144 KiB

safety

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int nmax = 200002;
ll S[nmax];
ll dp[5005][5005];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N;
    ll H;
    cin >> N >> H;
    for(int i=1; i<=N; i++) {
        cin >> S[i];
    }
    deque<pair<ll,ll>>dd;
    for(int i=0; i<=5000; i++) dp[1][i] = abs(S[1]-i);
    for(int i=2; i<=N; i++) {
        dd.clear();
        for(int j=0; j<=min(5000ll, H); j++) {
            while(!dd.empty() && dd.back().fi > dp[i-1][j]) {
                dd.pop_back();
            }
            dd.push_back({dp[i-1][j],j});
        }
        pair<ll,ll>sem;
        for(int j=0; j<=5000; j++) {
            if(!dd.empty() && dd.front().se < j-H) {
                dd.pop_front();
            }
            sem = dd.front();
            dp[i][j] = sem.fi + abs(S[i]-j);
            if(j-H+1 <= 5000) {
                while(!dd.empty() && dd.back().fi > dp[i-1][j+H+1]) {
                    dd.pop_back();
                }
                dd.push_back({dp[i-1][j+H+1], j+H+1});
            }
        }
    }
    ll jwb = LLONG_MAX;
    for(int i=0; i<=5000; i++) {
        jwb = min(jwb, dp[N][i]);
    }
    cout << jwb << endl;
    return 0;
}

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