oj.uz

Submission #246263

# Submission time Handle Problem Language Result Execution time Memory
246263 2020-07-08T13:09:03 Z SamAnd Safety (NOI18_safety) C++17
13 / 100
 176 ms 8312 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 * 3, m = 5000;
const ll INF = 1000000009000000009;

int n, h;
int a[N];

ll dp[N][N];

ll t[N * 4];

void bil(int tl, int tr, ll 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]);
}

ll 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]);

    vector<int> v;
    for (int i = 1; i <= n; ++i)
    {
        v.push_back(max(0, a[i] - h));
        v.push_back(a[i]);
        v.push_back(a[i] + h);
    }
    sort(all(v));

    for (int j = 0; j < sz(v); ++j)
    {
        dp[1][j] = abs(a[1] - v[j]);
    }
    for (int i = 2; i <= n; ++i)
    {
        bil(0, sz(v) - 1, dp[i - 1], 1);
        for (int j = 0; j < sz(v); ++j)
        {
            int l = lower_bound(all(v), v[j] - h) - v.begin();
            int r = upper_bound(all(v), v[j] + h) - v.begin() - 1;
            dp[i][j] = abs(a[i] - v[j]) + qry(0, sz(v) - 1, l, r, 1);
        }
    }
    ll ans = INF;
    for (int j = 0; j < sz(v); ++j)
        ans = min(ans, dp[n][j]);
    printf("%lld\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:47: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:49: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 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 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 8 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 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 160 ms 8312 KB Output is correct
14 Correct 117 ms 7928 KB Output is correct
15 Correct 96 ms 7928 KB Output is correct
16 Correct 68 ms 8312 KB Output is correct
17 Correct 92 ms 6776 KB Output is correct
18 Correct 68 ms 5116 KB Output is correct
19 Correct 136 ms 7800 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 160 ms 8312 KB Output is correct
14 Correct 117 ms 7928 KB Output is correct
15 Correct 96 ms 7928 KB Output is correct
16 Correct 68 ms 8312 KB Output is correct
17 Correct 92 ms 6776 KB Output is correct
18 Correct 68 ms 5116 KB Output is correct
19 Correct 136 ms 7800 KB Output is correct
20 Correct 123 ms 7392 KB Output is correct
21 Correct 176 ms 8312 KB Output is correct
22 Correct 95 ms 6264 KB Output is correct
23 Correct 61 ms 5380 KB Output is correct
24 Incorrect 114 ms 7548 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 160 ms 8312 KB Output is correct
14 Correct 117 ms 7928 KB Output is correct
15 Correct 96 ms 7928 KB Output is correct
16 Correct 68 ms 8312 KB Output is correct
17 Correct 92 ms 6776 KB Output is correct
18 Correct 68 ms 5116 KB Output is correct
19 Correct 136 ms 7800 KB Output is correct
20 Correct 123 ms 7392 KB Output is correct
21 Correct 176 ms 8312 KB Output is correct
22 Correct 95 ms 6264 KB Output is correct
23 Correct 61 ms 5380 KB Output is correct
24 Incorrect 114 ms 7548 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

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

Subtask #9
0 / 29.0

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