Submission #1311461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311461		samarthkulkarni	Safety (NOI18_safety)	C++20	5 / 100	26 ms	1928 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;

	sort(all(a));

	ll k = a[n/2];

	ll ans = 0;
	for (auto val : a) {ans += abs(val-k);}
	cout << ans << endl;

	// 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: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 5 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29