Submission #878025

#	Time	Username	Problem	Language	Result	Execution time	Memory
878025		fanwen	Safety (NOI18_safety)	C++17	35 / 100	146 ms	196696 KiB

safety

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \

const int MAX = 2e5 + 5;

int N, H, A[MAX];

namespace sub3 {
	bool check() {
		return N <= 10 && H <= 2;
	}

	int get_id(int val) {
		static int cnt = 0;
		static map <int, int> comp;
		if(comp.count(val)) return comp[val];
		return comp[val] = ++cnt;
	}

	int dp[11][1005];

}

namespace sub7 {
	bool check() {
		return N <= 5000 && *max_element(A + 1, A + N + 1) <= 5000;
	}

	long long dp[5005][5005];

	void solve() {
		int MaxA = *max_element(A + 1, A + N + 1);
		memset(dp, 0x3f, sizeof dp);
		memset(dp[0], 0, sizeof dp[0]);
		for (int i = 1; i <= N; ++i) {
			deque <int> q;
			int j = 0;
			for (int h = 0; h <= MaxA; ++h) {
				int l = max(0, h - H), r = min(MaxA, h + H);
				while(j <= r) {
					while(!q.empty() && dp[i - 1][q.back()] >= dp[i - 1][j]) q.pop_back();
					q.push_back(j);
					j++;
				}
				while(!q.empty() && h - q.front() > H) q.pop_front();
				if(!q.empty()) dp[i][h] = dp[i - 1][q.front()] + abs(h - A[i]);
			}
		}
		cout << *min_element(dp[N], dp[N] + MaxA + 1); 
		exit(0);
	}
}

void you_make_it(void) {
    cin >> N >> H;
    for (int i = 1; i <= N; ++i) cin >> A[i];
    if(sub7::check()) sub7::solve();
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("SAFETY");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

safety.cpp: In function 'void sub7::solve()':
safety.cpp:47:9: warning: unused variable 'l' [-Wunused-variable]
   47 |     int l = max(0, h - H), r = min(MaxA, h + H);
      |         ^
safety.cpp: In function 'int main()':
safety.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("SAFETY");
      |     ^~~~
safety.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("SAFETY");
      |     ^~~~

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