oj.uz

답안 #781513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781513 2023-07-13T07:15:34 Z acatmeowmeow Stove (JOI18_stove) C++11
20 / 100
 1000 ms 47684 KB 
#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));
	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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 17 ms 2888 KB Output is correct
12 Correct 637 ms 24148 KB Output is correct
13 Execution timed out 1084 ms 47684 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 17 ms 2888 KB Output is correct
12 Correct 637 ms 24148 KB Output is correct
13 Execution timed out 1084 ms 47684 KB Time limit exceeded
14 Halted 0 ms 0 KB -