oj.uz

Submission #1000718

# Submission time Handle Problem Language Result Execution time Memory
1000718 2024-06-18T07:35:53 Z vjudge1 Safety (NOI18_safety) C++17
18 / 100
 161 ms 21268 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int a[200100];

void solve(){
    int n, h;
    cin>>n>>h;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    multiset<ll> ql, qr;
    ql.insert(a[1]);
    qr.insert(a[1]);
    ll ans = 0;
    for(int i=2; i<=n; i++){
        ll add = h * (i - 1);
        ll l=*ql.rbegin()-add, r=*qr.begin()+add;
        ll t = a[i];
        if(l <= t and t <= r){
            ql.insert(t+add);
            qr.insert(t-add);
        }
        else if(l > t){
            ans += l-t;
            qr.insert(l-add);
            ql.erase(ql.find(l + add));
            ql.insert(t+add);
            ql.insert(t+add);
        }
        else if(r < t){
            ans += t - r;
            ql.insert(r+add);
            qr.erase(qr.find(r - add));
            qr.insert(t-add);
            qr.insert(t-add);
        }
    } 
    cout<<ans<<'\n';
}



int main(){
    solve();
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14424 KB Output is correct
2 Correct 141 ms 20308 KB Output is correct
3 Correct 161 ms 21268 KB Output is correct

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -