oj.uz

Submission #246259

# Submission time Handle Problem Language Result Execution time Memory
246259 2020-07-08T12:56:50 Z SamAnd Safety (NOI18_safety) C++17
24 / 100
 2000 ms 65676 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 5003, m = 5000, INF = 1000000009;

int n, h;
int a[N];

int dp[N][N];

int t[N * 4];

void bil(int tl, int tr, int a[], int pos)
{
    if (tl == tr)
    {
        t[pos] = a[tl];
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, a, pos * 2);
    bil(m + 1, tr, a, pos * 2 + 1);
    t[pos] = min(t[pos * 2], t[pos * 2 + 1]);
}

int qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return INF;
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return min(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

void solv()
{
    scanf("%d%d", &n, &h);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int j = 0; j <= m; ++j)
    {
        dp[1][j] = abs(a[1] - j);
    }
    for (int i = 2; i <= n; ++i)
    {
        bil(0, m, dp[i - 1], 1);
        for (int j = 0; j <= m; ++j)
        {
            dp[i][j] = abs(a[i] - j) + qry(0, m, max(0, j - h), min(m, j + h), 1);
        }
    }
    int ans = INF;
    for (int j = 0; j <= m; ++j)
        ans = min(ans, dp[n][j]);
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message

safety.cpp: In function 'void solv()':
safety.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &h);
     ~~~~~^~~~~~~~~~~~~~~~
safety.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 11 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 10 ms 640 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 768 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 11 ms 640 KB Output is correct
4 Correct 14 ms 768 KB Output is correct
5 Correct 13 ms 640 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9 ms 512 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 11 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 13 ms 768 KB Output is correct
9 Correct 13 ms 768 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 14 ms 768 KB Output is correct
12 Correct 13 ms 640 KB Output is correct
13 Correct 368 ms 10232 KB Output is correct
14 Correct 278 ms 9848 KB Output is correct
15 Correct 32 ms 9856 KB Output is correct
16 Correct 438 ms 10204 KB Output is correct
17 Correct 387 ms 8996 KB Output is correct
18 Correct 332 ms 7672 KB Output is correct
19 Correct 295 ms 9748 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 11 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 13 ms 768 KB Output is correct
9 Correct 13 ms 768 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 14 ms 768 KB Output is correct
12 Correct 13 ms 640 KB Output is correct
13 Correct 368 ms 10232 KB Output is correct
14 Correct 278 ms 9848 KB Output is correct
15 Correct 32 ms 9856 KB Output is correct
16 Correct 438 ms 10204 KB Output is correct
17 Correct 387 ms 8996 KB Output is correct
18 Correct 332 ms 7672 KB Output is correct
19 Correct 295 ms 9748 KB Output is correct
20 Correct 140 ms 9720 KB Output is correct
21 Correct 415 ms 10236 KB Output is correct
22 Correct 245 ms 8568 KB Output is correct
23 Correct 28 ms 7928 KB Output is correct
24 Correct 307 ms 9592 KB Output is correct
25 Correct 166 ms 8056 KB Output is correct
26 Correct 440 ms 10236 KB Output is correct
27 Correct 322 ms 9464 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 11 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 13 ms 768 KB Output is correct
9 Correct 13 ms 768 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 14 ms 768 KB Output is correct
12 Correct 13 ms 640 KB Output is correct
13 Correct 368 ms 10232 KB Output is correct
14 Correct 278 ms 9848 KB Output is correct
15 Correct 32 ms 9856 KB Output is correct
16 Correct 438 ms 10204 KB Output is correct
17 Correct 387 ms 8996 KB Output is correct
18 Correct 332 ms 7672 KB Output is correct
19 Correct 295 ms 9748 KB Output is correct
20 Correct 140 ms 9720 KB Output is correct
21 Correct 415 ms 10236 KB Output is correct
22 Correct 245 ms 8568 KB Output is correct
23 Correct 28 ms 7928 KB Output is correct
24 Correct 307 ms 9592 KB Output is correct
25 Correct 166 ms 8056 KB Output is correct
26 Correct 440 ms 10236 KB Output is correct
27 Correct 322 ms 9464 KB Output is correct
28 Execution timed out 2086 ms 65676 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 11 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 13 ms 768 KB Output is correct
9 Correct 13 ms 768 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 14 ms 768 KB Output is correct
12 Correct 13 ms 640 KB Output is correct
13 Incorrect 10 ms 640 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 11 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 13 ms 768 KB Output is correct
9 Correct 13 ms 768 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 14 ms 768 KB Output is correct
12 Correct 13 ms 640 KB Output is correct
13 Incorrect 10 ms 640 KB Output isn't correct
14 Halted 0 ms 0 KB -