oj.uz

Submission #355368

# Submission time Handle Problem Language Result Execution time Memory
355368 2021-01-22T12:15:10 Z gratus907 Safety (NOI18_safety) C++17
13 / 100
 2000 ms 203500 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

const int MN = 5050;
int N, H;
int s[MN];
int dp[MN][MN]; // (1-i)th, h[n] = j
int32_t main()
{
    usecppio
    cin >> N >> H;
    memset(dp, 0x7f, sizeof(dp));
    memset(dp[0], 0, sizeof(dp[0]));
    int MH = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> s[i];
        MH = max(MH, s[i]);
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= MH; j++)
        {
            int lb = max(j - H, 0);
            int ub = min(j + H, MH);
            for (int lst = lb; lst <= ub; lst++)
                dp[i][j] = min(dp[i-1][lst] + abs(j - s[i]), dp[i][j]);
        }
    }
    int ans = dp[N][0];
    for (int i = 1; i <= MH; i++)
        ans = min(dp[N][i], ans);
    cout << ans << '\n';
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100204 KB Output is correct
2 Correct 49 ms 100180 KB Output is correct
3 Correct 54 ms 100204 KB Output is correct
4 Correct 48 ms 100204 KB Output is correct
5 Correct 49 ms 100204 KB Output is correct
6 Correct 49 ms 100204 KB Output is correct
7 Correct 51 ms 100204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 100204 KB Output is correct
2 Correct 49 ms 100204 KB Output is correct
3 Correct 51 ms 100332 KB Output is correct
4 Correct 49 ms 100204 KB Output is correct
5 Correct 49 ms 100204 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 808 ms 203500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 202988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100204 KB Output is correct
2 Correct 49 ms 100180 KB Output is correct
3 Correct 54 ms 100204 KB Output is correct
4 Correct 48 ms 100204 KB Output is correct
5 Correct 49 ms 100204 KB Output is correct
6 Correct 49 ms 100204 KB Output is correct
7 Correct 51 ms 100204 KB Output is correct
8 Correct 54 ms 100204 KB Output is correct
9 Correct 49 ms 100204 KB Output is correct
10 Correct 51 ms 100332 KB Output is correct
11 Correct 49 ms 100204 KB Output is correct
12 Correct 49 ms 100204 KB Output is correct
13 Correct 74 ms 100204 KB Output is correct
14 Correct 51 ms 100204 KB Output is correct
15 Correct 471 ms 100224 KB Output is correct
16 Correct 321 ms 100212 KB Output is correct
17 Correct 421 ms 100332 KB Output is correct
18 Correct 314 ms 100332 KB Output is correct
19 Correct 53 ms 100204 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100204 KB Output is correct
2 Correct 49 ms 100180 KB Output is correct
3 Correct 54 ms 100204 KB Output is correct
4 Correct 48 ms 100204 KB Output is correct
5 Correct 49 ms 100204 KB Output is correct
6 Correct 49 ms 100204 KB Output is correct
7 Correct 51 ms 100204 KB Output is correct
8 Correct 54 ms 100204 KB Output is correct
9 Correct 49 ms 100204 KB Output is correct
10 Correct 51 ms 100332 KB Output is correct
11 Correct 49 ms 100204 KB Output is correct
12 Correct 49 ms 100204 KB Output is correct
13 Correct 74 ms 100204 KB Output is correct
14 Correct 51 ms 100204 KB Output is correct
15 Correct 471 ms 100224 KB Output is correct
16 Correct 321 ms 100212 KB Output is correct
17 Correct 421 ms 100332 KB Output is correct
18 Correct 314 ms 100332 KB Output is correct
19 Correct 53 ms 100204 KB Output is correct
20 Execution timed out 2065 ms 100204 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100204 KB Output is correct
2 Correct 49 ms 100180 KB Output is correct
3 Correct 54 ms 100204 KB Output is correct
4 Correct 48 ms 100204 KB Output is correct
5 Correct 49 ms 100204 KB Output is correct
6 Correct 49 ms 100204 KB Output is correct
7 Correct 51 ms 100204 KB Output is correct
8 Correct 54 ms 100204 KB Output is correct
9 Correct 49 ms 100204 KB Output is correct
10 Correct 51 ms 100332 KB Output is correct
11 Correct 49 ms 100204 KB Output is correct
12 Correct 49 ms 100204 KB Output is correct
13 Correct 74 ms 100204 KB Output is correct
14 Correct 51 ms 100204 KB Output is correct
15 Correct 471 ms 100224 KB Output is correct
16 Correct 321 ms 100212 KB Output is correct
17 Correct 421 ms 100332 KB Output is correct
18 Correct 314 ms 100332 KB Output is correct
19 Correct 53 ms 100204 KB Output is correct
20 Execution timed out 2065 ms 100204 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100204 KB Output is correct
2 Correct 49 ms 100180 KB Output is correct
3 Correct 54 ms 100204 KB Output is correct
4 Correct 48 ms 100204 KB Output is correct
5 Correct 49 ms 100204 KB Output is correct
6 Correct 49 ms 100204 KB Output is correct
7 Correct 51 ms 100204 KB Output is correct
8 Correct 54 ms 100204 KB Output is correct
9 Correct 49 ms 100204 KB Output is correct
10 Correct 51 ms 100332 KB Output is correct
11 Correct 49 ms 100204 KB Output is correct
12 Correct 49 ms 100204 KB Output is correct
13 Runtime error 808 ms 203500 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100204 KB Output is correct
2 Correct 49 ms 100180 KB Output is correct
3 Correct 54 ms 100204 KB Output is correct
4 Correct 48 ms 100204 KB Output is correct
5 Correct 49 ms 100204 KB Output is correct
6 Correct 49 ms 100204 KB Output is correct
7 Correct 51 ms 100204 KB Output is correct
8 Correct 54 ms 100204 KB Output is correct
9 Correct 49 ms 100204 KB Output is correct
10 Correct 51 ms 100332 KB Output is correct
11 Correct 49 ms 100204 KB Output is correct
12 Correct 49 ms 100204 KB Output is correct
13 Runtime error 808 ms 203500 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -