답안 #947811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947811	2024-03-17T04:28:19 Z	brendonw	Rabbit Carrot (LMIO19_triusis)	C++17	14 / 100	1000 ms	79700 KB

triusis

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MAX_A = 5e3;

int solve() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (auto &a_i: a) {
		cin >> a_i;
	}
	vector<vector<int>> dp(n + 1, vector<int>(MAX_A + 1, 3e5));
	dp[0] = {0};
	for (int i = 1; i <= n; ++i) {
		for (int h = 0; h <= MAX_A; ++h) {
			int prev = INT_MAX;
			for (int j = max(h - m, 0); j <= MAX_A; ++j) {
				prev = min(prev, dp[i - 1][j]);
			}
			dp[i][h] = (a[i - 1] != h) + prev;
		}
	}
	cout << *min_element(dp[n].begin(), dp[n].end());

	return 0;
}

#ifndef MY_UNIT_TEST

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

#endif

Subtask #1

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	344 KB	Output is correct
2	Correct	12 ms	520 KB	Output is correct
3	Correct	23 ms	348 KB	Output is correct
4	Correct	115 ms	668 KB	Output is correct
5	Correct	116 ms	668 KB	Output is correct
6	Correct	115 ms	600 KB	Output is correct
7	Correct	115 ms	600 KB	Output is correct
8	Correct	116 ms	668 KB	Output is correct
9	Correct	230 ms	852 KB	Output is correct
10	Correct	116 ms	668 KB	Output is correct
11	Correct	133 ms	664 KB	Output is correct
12	Correct	115 ms	604 KB	Output is correct
13	Correct	116 ms	668 KB	Output is correct
14	Correct	115 ms	600 KB	Output is correct
15	Correct	115 ms	668 KB	Output is correct
16	Correct	115 ms	600 KB	Output is correct

Subtask #2

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	344 KB	Output is correct
2	Correct	12 ms	520 KB	Output is correct
3	Correct	23 ms	348 KB	Output is correct
4	Correct	115 ms	668 KB	Output is correct
5	Correct	116 ms	668 KB	Output is correct
6	Correct	115 ms	600 KB	Output is correct
7	Correct	115 ms	600 KB	Output is correct
8	Correct	116 ms	668 KB	Output is correct
9	Correct	230 ms	852 KB	Output is correct
10	Correct	116 ms	668 KB	Output is correct
11	Correct	133 ms	664 KB	Output is correct
12	Correct	115 ms	604 KB	Output is correct
13	Correct	116 ms	668 KB	Output is correct
14	Correct	115 ms	600 KB	Output is correct
15	Correct	115 ms	668 KB	Output is correct
16	Correct	115 ms	600 KB	Output is correct
17	Correct	67 ms	596 KB	Output is correct
18	Correct	39 ms	524 KB	Output is correct
19	Correct	23 ms	348 KB	Output is correct
20	Execution timed out	1054 ms	79700 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	596 KB	Output is correct
2	Correct	39 ms	524 KB	Output is correct
3	Correct	23 ms	348 KB	Output is correct
4	Execution timed out	1054 ms	79700 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	596 KB	Output is correct
2	Correct	39 ms	524 KB	Output is correct
3	Correct	23 ms	348 KB	Output is correct
4	Execution timed out	1054 ms	79700 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-