제출 #1288634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288634		yonatanl	Safety (NOI18_safety)	C++20	7 / 100	160 ms	327680 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 = n * (*(max_element(arr.begin(), arr.end())));
	vvll dp(n, vll(MAX_H, INF));
	rep(j, 0, MAX_H) {
		dp[0][j] = abs(arr[0] - j);
	}
	rep(i, 1, n) {
		rep(j, 0, MAX_H) {
			rep(k, max(j - H, (ll)0), min(MAX_H, j + H + 1)) {
				upmin(dp[i][j], dp[i - 1][k] + abs(arr[i] - j));
			}
		}
	}
	ll res = INF;
	rep(j, 0, MAX_H) upmin(res, dp[n - 1][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: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29