Submission #1269675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269675		ducdev	Safety (NOI18_safety)	C++17	40 / 100	158 ms	98436 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;

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

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

    void Solve() {
        sort(a + 1, a + n + 1);
        ll res = 0;
        for (int i = 1; i <= n; i++) res += abs(a[i] - a[(n + 1) >> 1]);
        cout << res;
    };
};  // namespace SUBTASK_4

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_4::checkSubtask())
      return SUBTASK_4::Solve(), 0;
    SUBTASK_127::Solve();
};

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 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