oj.uz

Submission #878037

# Submission time Handle Problem Language Result Execution time Memory
878037 2023-11-24T03:18:14 Z atarii Safety (NOI18_safety) C++17
49 / 100
 179 ms 2908 KB 
#include<bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define ll long long
#define foru(i, a, b, k) for(int i = a; i <= b; i += k)
#define umap unordered_map
#define pii pair<int, int>
#define ford(i, a, b, k) for(int i = a; i >= b; i -= k)
#define vint vector <int>
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
#define pb push_back
#define sz(s) (int)s.size()
#define ctn continue
#define ld long double

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
template<typename T> ll power(T a, const T b) { ll res = 1, x = a, y = b; while(y){if(y & 1)res *= x; x = x * x; y>>=1;}; return res; }
template<typename T> ll modpower(T a, T b, const T &m) { ll res = 1, x = a, y = b; x %= m; while(y){if(y & 1){res *= x; res %= m;}; x = x * x; x %= m; y >>= 1; } return res % m; }
template<typename T> T __lcm(T &a, T &b) { return a / __gcd(a, b) * b; }

template <typename T> bool getbit(T val, int i) { return (val >> i) & 1; }
template <typename T> int cntbit(T val)        { int cnt = 0; for( ; val; val -= val & (-val)) ++cnt; return cnt; }
template <typename T> T offbit(T val, int i) { return val & (~(T(1) << i)); }
template <typename T> T onbit(T val, int i) { return val | (T(1) << i); }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

template <typename _Tp> void write_unsign(const _Tp &__n) { if (__n > 9) { write_unsign(__n / 10); } putchar(__n % 10 + '0'); }
void write(const int       &__n) { if (__n < 0) { putchar('-'); write_unsign(-__n); } else { write_unsign(__n); } }
void write(const long long &__n) { if (__n < 0) { putchar('-'); write_unsign(-__n); } else { write_unsign(__n); } }
void write(const unsigned long long &__n) { if (__n < 0) { putchar('-'); write_unsign(-__n); } else { write_unsign(__n); } }
void write(const char      &__c) {                                                                putchar(__c);   }
void write(const string    &__s) { for (auto &__c : __s) {                                         putchar(__c); } }
template <typename _Tp, typename... _Ts> void write(const _Tp &__x, const _Ts &...__y) { write(__x), write(__y...); }

const  ll  MOD = 1e9 + 7;
const  ll  LIM = 1e6 + 10;
const int    N = 2e5 + 5;
const int  INF = 0x3f3f3f3f;
const  ll LINF = 1e17 + 100;
const int  LOG = 19;
const ll  base = 31;
const int offset = 1e3 + 1;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int mul(int a, int b) { a %= MOD, b %= MOD; return 1LL * a * b % MOD; }
inline int sub(int a, int b) { a -= b; if(a < 0) a += MOD; return a; }
inline int add(int a, int b) { a += b; if(a >= MOD) a -= MOD; return a; }

int n, h;
int a[N];
int pre[N], cur[N];

void read()
{
    n = readInt();
    h = readInt();
    foru(i, 1, n, 1) a[i] = readInt();
}

namespace subtask3
{
    int p[N];

    void try0(int id, ll &minVal, ll sum)
    {
        if(id == 0) return minimize(minVal, sum), void();
        if(sum >= minVal) return;

        foru(cur, max(0, p[id + 1] - h), p[id + 1] + h, 1)
        {
            p[id] = cur;
            try0(id - 1, minVal, sum + abs(a[id] - p[id]));
        }
    }

    void try1(int id, ll &minVal, ll sum)
    {
        if(id == n + 1) return minimize(minVal, sum), void();
        if(sum >= minVal) return;

        foru(cur, max(0, p[id - 1] - h), p[id - 1] + h, 1)
        {
            p[id] = cur;
            try1(id + 1, minVal, sum + abs(a[id] - p[id]));
        }
    }

    void solve()
    {
        ll res = LINF;
        foru(i, 1, n, 1)
        {
            ll res0 = LINF, res1 = LINF;
            foru(j, 1, n, 1) p[j] = 0;
            p[i] = a[i];

            try0(i - 1, res0, 0);
            try1(i + 1, res1, 0);

            minimize(res, res0 + res1);
        }
        cout << res;
    }
}

namespace subtask4
{
    void solve()
    {
        sort(a + 1, a + 1 + n);
        ll res = 0;
        foru(i, 1, n, 1) res += abs(a[(n + 1) / 2] - a[i]);
        cout << res;
    }
}

void insert(deque <int> &q, int rb)
{
    while(!q.empty() && pre[q.back()] >= pre[rb]) q.pop_back();
    q.pb(rb);
}

void remove(deque <int> &q, int lb)
{
    while(!q.empty() && q.front() < lb) q.pop_front();
}

namespace subtask7
{
    void solve()
    {
        int liml = *min_element(a + 1, a + 1 + n);
        int limr = *max_element(a + 1, a + 1 + n);

        if(h >= *max_element(a + 1, a + 1 + n)) return cout << 0, void();

        deque <int> q; q.clear();

        foru(i, 1, n, 1)
        {
            int lb = liml, rb = min(limr, liml + h);

            q.clear();
            foru(i, lb, rb, 1)
            {
                while(!q.empty() && pre[q.back()] >= pre[i]) q.pop_back();
                q.pb(i);
            }

            foru(j, liml, limr, 1)
            {
                if(j > liml)
                {
                    if(rb + 1 <= limr) insert(q, ++rb);
                    if(j - h > liml) remove(q, ++lb);
                }
                cur[j] = abs(a[i] - j) + pre[q.front()];
            }

            foru(j, liml, limr, 1) pre[j] = cur[j];
        }

        int res = INF;
        foru(j, liml, limr, 1) minimize(res, cur[j]);
        cout << res;
    }
}

void solve()
{
    if(h == 0) return subtask4::solve();
    if(n <= 10 && h <= 2) return subtask3::solve();
    subtask7::solve();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    #define file "safety"
    if(fopen(file".inp", "r"))
    {
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }

    read();
    solve();
    return 0;
}

Compilation message

safety.cpp: In function 'int main()':
safety.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:193:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.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 348 KB Output is correct
4 Correct 1 ms 344 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 860 KB Output is correct
2 Correct 18 ms 1116 KB Output is correct
3 Correct 19 ms 1116 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 13 ms 348 KB Output is correct
21 Correct 17 ms 536 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 16 ms 344 KB Output is correct
25 Correct 19 ms 344 KB Output is correct
26 Correct 17 ms 344 KB Output is correct
27 Correct 19 ms 348 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 13 ms 348 KB Output is correct
21 Correct 17 ms 536 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 16 ms 344 KB Output is correct
25 Correct 19 ms 344 KB Output is correct
26 Correct 17 ms 344 KB Output is correct
27 Correct 19 ms 348 KB Output is correct
28 Correct 179 ms 520 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 154 ms 348 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 146 ms 596 KB Output is correct
33 Correct 164 ms 520 KB Output is correct
34 Correct 109 ms 344 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 13 ms 348 KB Output is correct
27 Correct 17 ms 536 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 16 ms 344 KB Output is correct
31 Correct 19 ms 344 KB Output is correct
32 Correct 17 ms 344 KB Output is correct
33 Correct 19 ms 348 KB Output is correct
34 Correct 179 ms 520 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 154 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 146 ms 596 KB Output is correct
39 Correct 164 ms 520 KB Output is correct
40 Correct 109 ms 344 KB Output is correct
41 Runtime error 4 ms 2908 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 12 ms 860 KB Output is correct
20 Correct 18 ms 1116 KB Output is correct
21 Correct 19 ms 1116 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 13 ms 348 KB Output is correct
30 Correct 17 ms 536 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 16 ms 344 KB Output is correct
34 Correct 19 ms 344 KB Output is correct
35 Correct 17 ms 344 KB Output is correct
36 Correct 19 ms 348 KB Output is correct
37 Correct 179 ms 520 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 154 ms 348 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 146 ms 596 KB Output is correct
42 Correct 164 ms 520 KB Output is correct
43 Correct 109 ms 344 KB Output is correct
44 Runtime error 4 ms 2908 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -