oj.uz

Submission #648762

# Submission time Handle Problem Language Result Execution time Memory
648762 2022-10-08T06:40:20 Z I_am_balancing Safety (NOI18_safety) C++17
18 / 100
 305 ms 8204 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 6 ms 8144 KB Output is correct
6 Correct 5 ms 8136 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8160 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2508 KB Output is correct
2 Correct 37 ms 3660 KB Output is correct
3 Correct 36 ms 3720 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 6 ms 8144 KB Output is correct
6 Correct 5 ms 8136 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 4 ms 8160 KB Output is correct
11 Correct 5 ms 8140 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 19 ms 8148 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 305 ms 8196 KB Output is correct
16 Correct 187 ms 8148 KB Output is correct
17 Correct 245 ms 8188 KB Output is correct
18 Correct 174 ms 8204 KB Output is correct
19 Correct 7 ms 8148 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 6 ms 8144 KB Output is correct
6 Correct 5 ms 8136 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 4 ms 8160 KB Output is correct
11 Correct 5 ms 8140 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 19 ms 8148 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 305 ms 8196 KB Output is correct
16 Correct 187 ms 8148 KB Output is correct
17 Correct 245 ms 8188 KB Output is correct
18 Correct 174 ms 8204 KB Output is correct
19 Correct 7 ms 8148 KB Output is correct
20 Incorrect 1 ms 328 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 6 ms 8144 KB Output is correct
6 Correct 5 ms 8136 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 4 ms 8160 KB Output is correct
11 Correct 5 ms 8140 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 19 ms 8148 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 305 ms 8196 KB Output is correct
16 Correct 187 ms 8148 KB Output is correct
17 Correct 245 ms 8188 KB Output is correct
18 Correct 174 ms 8204 KB Output is correct
19 Correct 7 ms 8148 KB Output is correct
20 Incorrect 1 ms 328 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 6 ms 8144 KB Output is correct
6 Correct 5 ms 8136 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 4 ms 8160 KB Output is correct
11 Correct 5 ms 8140 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 6 ms 8144 KB Output is correct
6 Correct 5 ms 8136 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 4 ms 8160 KB Output is correct
11 Correct 5 ms 8140 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -