Submission #1269673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269673		ducdev	Safety (NOI18_safety)	C++17	4 / 100	73 ms	99400 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 {

};

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 < 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];
    };

    SUBTASK_127::Solve();
};

Compilation message (stderr)

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

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