답안 #781514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
781514	2023-07-13T07:16:48 Z	acatmeowmeow	Stove (JOI18_stove)	C++11	50 / 100	300 ms	262144 KB

stove

#include <bits/stdc++.h>

using namespace std;

#define int long long 

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<int> arr(n + 5);
	for (int i = 1; i <= n; i++) cin >>arr[i];
	vector<vector<int>> dp(n + 5, vector<int>(k + 5, 1e18));
	unordered_map<int, int> mn;
	//for (int i = 0; i <= k; i++) mn[i] = 0;
	//mn[0] = 0;
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (!mn.count(j - 1)) mn[j - 1] = 1e18;
			dp[i][j] = min(dp[i][j], arr[i] + mn[j - 1]);
			mn[j - 1] = min(mn[j - 1], dp[i - 1][j - 1] - arr[i] + 1);
			dp[i][j] = min(dp[i][j], arr[i] + mn[j - 1]);
		}	
	}
	cout << dp[n][k] << '\n';
	return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	2 ms	724 KB	Output is correct
11	Correct	10 ms	2900 KB	Output is correct
12	Correct	98 ms	24100 KB	Output is correct
13	Correct	174 ms	47664 KB	Output is correct
14	Correct	255 ms	68916 KB	Output is correct
15	Correct	258 ms	70912 KB	Output is correct

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	2 ms	724 KB	Output is correct
11	Correct	10 ms	2900 KB	Output is correct
12	Correct	98 ms	24100 KB	Output is correct
13	Correct	174 ms	47664 KB	Output is correct
14	Correct	255 ms	68916 KB	Output is correct
15	Correct	258 ms	70912 KB	Output is correct
16	Correct	42 ms	16844 KB	Output is correct
17	Correct	300 ms	87404 KB	Output is correct
18	Runtime error	99 ms	262144 KB	Execution killed with signal 9
19	Halted	0 ms	0 KB	-