Submission #1311460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311460		samarthkulkarni	Safety (NOI18_safety)	C++20	24 / 100	2095 ms	2496 KiB

safety

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


struct SegTree {
	vi a, tree;
	ll n;
	SegTree (const vi &temp) {
		a = temp;
		n = a.size();
		tree.resize(4*n);
	}

	void build(int id, int l, int r) {
		if (l == r) {
			tree[id] = a[l];
			return;
		}
		int mid = (l + r)/2;
		build(2*id, l, mid);
		build(2*id+1, mid+1, r);
		tree[id] = min(tree[2*id], tree[2*id+1]);
	}

	ll query(int id, int l, int r, int L, int R) {
		if (L > r || l > R) return 1e18;
		if (L <= l && R >= r) return tree[id];

		int mid = (l + r)/2;
		return min(query(2*id, l, mid, L, R), query(2*id+1, mid+1, r, L, R));
	}

	void build(){build(1, 0, n-1);}
	ll query(int l, int r) {
		l = max(l, 0);
		r = min(r, int(n-1));
		return query(1, 0, n-1, l, r);
	}
};




void solution() {
	ll n, h;
	cin >> n >> h;
	vi a(n);
	for (ll &z : a) cin >> z;


	ll mx = *max_element(all(a));
		
	h = min(h, mx);
	vi dp(mx+1);

	for (int i = 0; i < n; i++) {
		vi ndp(mx+1);
		SegTree m(dp);
		m.build();

		for (int j = 0; j <= mx; j++) {
			ndp[j] = abs(j-a[i]) + m.query(j-h, j+h);
		}

		dp = move(ndp);
	}

	cout << *min_element(all(dp)) << endl;
}

• 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: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29