Submission #124071

#TimeUsernameProblemLanguageResultExecution timeMemory
124071mechfrog88Safety (NOI18_safety)C++14
24 / 100
892 ms262148 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("unroll-loops,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; vector <vector<ll>> sparse(15,vector<ll>(5001)); void build(vector <ll> arr){ for (ll z=0;z<15;z++){ for (ll x=0;x<5001;x++){ sparse[z][x] = LLONG_MAX; if (x + (1 << z) - 1 < 5000){ if (z == 0) sparse[z][x] = arr[x]; else sparse[z][x] = min(sparse[z-1][x],sparse[z-1][x+(1<<(z-1))]); } } } } ll query (ll l ,ll r){ int k = 31-__builtin_clz(r-l); if (l == r) k = 0; return min(sparse[k][l],sparse[k][r - (1 << k)+1]); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll n,d; cin >> n >> d; vector <vector<ll>> dp(n+1,vector<ll>(5001,0)); vector <ll> arr(n+1); ll maxi = 0; for (int z=1;z<=n;z++){ cin >> arr[z]; maxi = max(maxi,arr[z]); } for (int z=1;z<=n;z++){ build(dp[z-1]); for (int h=0;h<=maxi;h++){ ll temp = query(max(ll(0),h-d),min(ll(maxi),h+d)); dp[z][h] = temp+abs(arr[z]-h); } } ll mini = LLONG_MAX; for(int z=0;z<=maxi;z++){ mini = min(dp[n][z],mini); } cout << mini << endl; }
#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...