제출 #1288641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288641		yonatanl	Safety (NOI18_safety)	C++20	24 / 100	2096 ms	1536 KiB

safety

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

//const ll MAX_H = 5005;

void solve() {
	ll n, H;
	cin >> n >> H;
	vll arr(n);
	rep(i, 0, n) cin >> arr[i];
	ll MAX_H = 2 * (*(max_element(arr.begin(), arr.end())));
	vll dp(MAX_H, INF);
	rep(j, 0, MAX_H) {
		dp[j] = abs(arr[0] - j);
	}
	rep(i, 1, n) {
		vll nextdp(MAX_H, INF);
		multiset<ll> s;
		rep(k, 0, min(MAX_H, H + 1)) {
			s.insert(dp[k]);
		}
		nextdp[0] = *s.begin() + abs(arr[i]);
		rep(j, 1, MAX_H) {
			if (j + H < MAX_H) {
				s.insert(dp[j + H]);
			}
			nextdp[j] = *(s.begin()) + abs(arr[i] - j);
			if (j - H >= 0) {
				auto it = s.find(dp[j - H]);
				s.erase(it);
			}
			/*
			rep(k, max(j - H, (ll)0), min(MAX_H, j + H + 1)) {
				upmin(nextdp[j], dp[k] + abs(arr[i] - j));
			}*/
		}
		swap(nextdp, dp);
	}
	ll res = INF;
	rep(j, 0, MAX_H) upmin(res, dp[j]);
	cout << res << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	solve();
}

• 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