제출 #548797

#제출 시각아이디문제언어결과실행 시간메모리
548797BelguteiSafety (NOI18_safety)C++17
9 / 100
40 ms2180 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 ll n,h; ll a[200005]; ll dp[10005]; ll tur[10005]; ll level,zereg[30]; vector<ll> v[30]; ll l,r; ll mn; ll mn1,mx1; void build_tree(){ zereg[0] = 1; for(int i = 0; i <= 30; i++){ if(zereg[i] >= 5000){ 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<=5000; 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); } ll solve(int pos){ int cnt=0; ll ret=0; for(int i=mn1; i<=mx1; i++){ dp[i] = abs(i-a[pos]); } for(int i = pos - 1; i >= 1; i--){ cnt++; ll zero=0; ret = 1e18; for(int j=max(a[i]-cnt*h,zero); j<=a[i]+cnt*h; j++){ tur[j]=dp[j]; dp[j] = 1e18; } for(int j=max(a[i]-cnt*h,zero); j<=a[i]+cnt*h; j++){ l=max(j-h,mn1); r=min(j+h,mx1); for(int k=l; k<=r; k++){ dp[k] = tur[j] + abs(j-a[i]); ret=min(ret,dp[k]); } } } debug(ret); // for(int i=mn1; i<=mx1; i++){ dp[i] = abs(i-a[pos]); } cnt = 0; ll ret1=0; for(int i = pos + 1; i <= n; i++){ cnt++; ll zero=0; ret1 = 1e18; for(int j=max(a[pos]-cnt*h,mn1); j<=min(a[pos]+cnt*h,mx1); j++){ debug(j); tur[j]=dp[j]; dp[j] = 1e18; } for(int j=max(a[pos]-(cnt-1)*h,mn1); j<=min(a[pos]+(cnt-1)*h,mx1); j++){ l=max(j-h,mn1); r=min(j+h,mx1); for(int k=l; k<=r; k++){ dp[k] = min(dp[k], tur[j] + abs(k-a[i])); ret1=min(ret1,dp[k]); } } } debug(ret1); return ret + ret1; } 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]); } debug(mn1); debug(mx1); if(n <= 10 && h <= 2){ // subtask 3 ll ans = 1e18; for(int i = 1; i <= n; i++){ // i - behlegdsen number ans=min(ans,solve(i)); break; } cout << ans; return 0; } 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); pre_sum += a[i]; } 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)); } } ll ans = 1e9; for(int i=0; i<=5000; i++){ ans=min(ans,dp[i]); } cout << ans; }

컴파일 시 표준 에러 (stderr) 메시지

safety.cpp: In function 'long long int solve(int)':
safety.cpp:103:12: warning: unused variable 'zero' [-Wunused-variable]
  103 |         ll zero=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...