oj.uz

Submission #527038

# Submission time Handle Problem Language Result Execution time Memory
527038 2022-02-16T20:52:16 Z niloyroot Safety (NOI18_safety) C++14
13 / 100
 2000 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
#define ff first
#define ss second
const ll mod = 1e9 + 7;
ll dp[5005][10005];

void solve(){
    ll n,h; cin>>n>>h;

    ll a[n+1];
    ll mx=0;
    forp(i,1,n){
        cin>>a[i];
        mx=max(mx,a[i]);
    }

    forp(i,1,n){
        forp(j,0,mx){
            dp[i][j]=INT_MAX;
        }
    }

    forp(i,1,n){
        forp(j,0,mx){
            forp(k,j,min(j+h,mx)){
                dp[i][j] = min(dp[i][j], dp[i-1][k]+abs(a[i]-j));
            }
            forn(k,j,max(0ll,j-h)){
                dp[i][j] = min(dp[i][j], dp[i-1][k]+abs(a[i]-j));
            }
        }
    }

    ll mn=INT_MAX;
    forp(i,0,mx){
        mn=min(mn,dp[n][i]);
    }

    cout<<mn<<newl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1; //cin>>t;
    while(t--)solve();
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 6 ms 3900 KB Output is correct
14 Correct 2 ms 3788 KB Output is correct
15 Correct 86 ms 3788 KB Output is correct
16 Correct 57 ms 3944 KB Output is correct
17 Correct 82 ms 3404 KB Output is correct
18 Correct 56 ms 2972 KB Output is correct
19 Correct 3 ms 3784 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 6 ms 3900 KB Output is correct
14 Correct 2 ms 3788 KB Output is correct
15 Correct 86 ms 3788 KB Output is correct
16 Correct 57 ms 3944 KB Output is correct
17 Correct 82 ms 3404 KB Output is correct
18 Correct 56 ms 2972 KB Output is correct
19 Correct 3 ms 3784 KB Output is correct
20 Execution timed out 2081 ms 20300 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 6 ms 3900 KB Output is correct
14 Correct 2 ms 3788 KB Output is correct
15 Correct 86 ms 3788 KB Output is correct
16 Correct 57 ms 3944 KB Output is correct
17 Correct 82 ms 3404 KB Output is correct
18 Correct 56 ms 2972 KB Output is correct
19 Correct 3 ms 3784 KB Output is correct
20 Execution timed out 2081 ms 20300 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Runtime error 106 ms 262148 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Runtime error 106 ms 262148 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -