Submission #648762

#	Time	Username	Problem	Language	Result	Execution time	Memory
648762		I_am_balancing	Safety (NOI18_safety)	C++17	18 / 100	305 ms	8204 KiB

safety

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using tl = tuple<ll,ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#define sz(x) ll((x).size())
#define pb emplace_back
#define F first
#define S second
const ll
  inf = (1ll<<62)
, N   = 2e5 + 1
, K   = 340
, mod = 1e9 + 7
;
ll n, h;
array<ll,N> a;

void solve1(){
    ll l = 0, r = 1e9+1;
    auto check = [&](ll mid){
        ll t = 0;
        for(ll i = 1;i<=n;i++)t+=abs(a[i]-mid);
        return t;
    };
    while(l+3<r){
        ll mid1 = l + (r-l)/3, mid2 = r - (r-l)/3;
        if(check(mid1) > check(mid2))l=mid1;
        else r = mid2;
    }
    ll ans = inf;
    for(ll i = l;i<=r;i++)ans=min(ans,check(i));
    cout << ans;
}

void solve2(){
    vector<vector<ll>> dp(1000,vector<ll>(1000,inf));
    fill(all(dp[0]),0);
    for(ll i = 0;i<=n;i++){
        if(i>0)for(ll j = 0;j<=400;j++){
            for(ll k = max(0ll,j-h);k<=min(400ll,j+h);k++){
                dp[i][j] = min(dp[i][j],dp[i-1][k] + abs(a[i]-j));
            }
        }
    }
    cout << *min_element(all(dp[n]));
}

void solve(){
    cin >> n >> h;
    for(ll i = 1;i<=n;i++){
        cin >> a[i];
    }
    if(h == 0){
        solve1();
    }
    else if(n<=500 && *max_element(all(a))<=500){
        solve2();
    }
}


void precalc(){}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    precalc();
    //cout << fixed << setprecision(10);
    //cin >> t;
    while(t--){
        solve();
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29