Submission #1208096

#TimeUsernameProblemLanguageResultExecution timeMemory
1208096loomSafety (NOI18_safety)C++20
35 / 100
316 ms327680 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define inf 5e18 #define nl '\n' const int k = 5000; inline void solve(){ int n, h; cin>>n>>h; int a[n]; for(int i=0; i<n; i++) cin>>a[i]; int dp[n][k+1]; for(int j=0; j<=k; j++) dp[0][j] = abs(a[0] - j); for(int i=1; i<n; i++){ deque<pair<int,int>> dq; for(int j=0; j<=min(h, k); j++){ while(!dq.empty() and dq.back().second >= dp[i-1][j]) dq.pop_back(); dq.push_back({j, dp[i-1][j]}); } dp[i][0] = dq.front().second + a[i]; for(int j=1; j<=k; j++){ if(dq.front().first == j-h-1) dq.pop_front(); if(j+h <= k){ while(!dq.empty() and dq.back().second >= dp[i-1][j+h]) dq.pop_back(); dq.push_back({j+h, dp[i-1][j+h]}); } dp[i][j] = dq.front().second + abs(a[i] - j); } } int ans = inf; for(int j=0; j<=k; j++) ans = min(ans, dp[n-1][j]); cout<<ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...