Submission #1269698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269698		ducdev	Safety (NOI18_safety)	C++17	49 / 100	167 ms	98432 KiB

safety

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX_N = 2e5;
const int MOD = 1e9 + 7;

template <class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x <= y) return false;
    x = y;
    return true;
};

int n, H;
int a[MAX_N + 5];
vector<int> compress;

namespace SUBTASK_4 {
    const int N = MAX_N;

    int c[N + 5];

    bool checkSubtask() {
        return H == 0;
    };

    void Solve() {
        for (int i = 1; i <= n; i++) c[i] = a[i];

        sort(c + 1, c + n + 1);

        ll res = 0;
        for (int i = 1; i <= n; i++) res += abs(c[i] - c[(n + 1) >> 1]);

        cout << res << '\n';
    };
};  // namespace SUBTASK_4

namespace SUBTASK_3 {
    const int N = 10;
    const ll INF = 1e18;

    bool checkSubtask() {
        return n <= N && H <= 2;
    };

    ll backtrack(int idx, int preVal, int dir, bool root) {
        if (idx < 1 || idx > n) return 0;

        ll ret = INF;
        if (root) {
            ret = backtrack(idx - 1, preVal, -1, 0) + backtrack(idx + 1, preVal, 1, 0);
        } else {
            int nextIdx = idx + dir;
            int low = max(preVal - H, 0);
            int high = preVal + H;
            for (int val = low; val <= high; val++) {
                minimize(ret, backtrack(nextIdx, val, dir, 0) + abs(val - a[idx]));
            };
        };

        return ret;
    };

    void Solve() {
        ll res = INF;

        for (int i = 1; i <= n; i++) minimize(res, backtrack(i, a[i], 0, true));

        cout << res << '\n';
    };
};  // namespace SUBTASK_3

namespace SUBTASK_127 {
    const int N = 5000;
    const int S = 5000;
    const int INF = 1e9;

    int dp[N + 5][S + 5];

    void Solve() {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= S; j++) {
                dp[i][j] = INF;
            };
        };

        for (int i = 0; i <= S; i++) dp[0][i] = 0;
        for (int i = 1; i <= n; i++) {
            deque<int> dq;
            for (int j = 0; j < min(S, H); j++) {
                while (!dq.empty() && dp[i - 1][dq.back()] >= dp[i - 1][j]) dq.pop_back();
                dq.push_back(j);
            };

            for (int j = 0; j <= S; j++) {
                while (!dq.empty() && dq.front() < max(0, j - H)) dq.pop_front();
                while (j + H <= S && !dq.empty() && dp[i - 1][dq.back()] >= dp[i - 1][j + H]) dq.pop_back();
                if (j + H <= S) dq.push_back(j + H);
                dp[i][j] = dp[i - 1][dq.front()] + abs(a[i] - j);
            };
        };

        int res = INF;
        for (int i = 0; i <= S; i++) res = min(res, dp[n][i]);

        cout << res << '\n';
    };
};  // namespace SUBTASK_127

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> n >> H;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    };

    if (SUBTASK_3::checkSubtask())
      return SUBTASK_3::Solve(), 0;
    if (SUBTASK_4::checkSubtask())
      return SUBTASK_4::Solve(), 0;
    SUBTASK_127::Solve();
};

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29