제출 #548767

#제출 시각아이디문제언어결과실행 시간메모리
548767BelguteiSafety (NOI18_safety)C++17
0 / 100
318 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define pb push_back #define mk make_pair #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); void debug_out() { cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); } #ifdef BE_DEBUG #define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__) #else #define debug(...) #endif int n,h; int a[200005]; int dp[10005]; int tur[10005]; int level,zereg[30]; vector<int> v[30]; int l,r; int mn; int mn1,mx1; void build_tree(){ zereg[0] = 1; for(int i = 0; i <= 30; i++){ if(zereg[i] >= mx1){ level = i; break; } zereg[i+1] = zereg[i] * 2; } for(int i=0; i<=level; i++){ for(int j=0; j<zereg[i]; j++){ v[i].pb(1e9); } } } void tree(){ for(int i=0; i<=mx1; i++){ v[level][i] = dp[i]; dp[i] = 1e9; } for(int i=level-1; i>=0; i--){ for(int j=0; j<zereg[i]; j++){ v[i][j]=min(v[i+1][j*2],v[i+1][j*2+1]); } } } void dfs(int k, int x){ int y=zereg[level-k]*x; int z=zereg[level-k]*(x+1)-1; if(l<=y && z<=r){ mn = min(mn,v[k][x]); return; } if(z<l || y>r || k==level) return; dfs(k+1,x*2); dfs(k+1,x*2+1); } int main() { IOS cin >> n >> h; mn1 = 1e9; for(int i = 1; i <= n; i++){ cin >> a[i]; mn1 = min(mn1,a[i]); mx1 = max(mx1,a[i]); } if(h==0){ sort(a+1,a+n+1); ll ans = 1e18; ll sum = 0; for(int i = 1; i <= n; i++){ sum += a[i]; } ll pre_sum = 0; for(int i = 1; i <= n; i++){ sum -= a[i]; ll tur = a[i] * (i-1); tur = tur - pre_sum; ll tur1 = a[i] * (n-i); tur1 = sum - tur1; ans=min(ans,tur + tur1); } cout << ans; return 0; } build_tree(); for(int i = 0; i <= 8192; i++){ dp[i] = abs(i - a[1]); } for(int i = 2; i <= n; i++){ tree(); for(int j = mn1; j <= mx1; j++){ // (j-h) -> (j+h) l = max(j-h,mn1); r = min(j+h,mx1); mn=1e9; dfs(0,0); dp[j] = min(dp[j],mn+abs(a[i]-j)); } } int ans = 1e9; for(int i=0; i<=5000; i++){ ans=min(ans,dp[i]); } cout << ans; }
#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...