oj.uz

Submission #1100948

# Submission time Handle Problem Language Result Execution time Memory
1100948 2024-10-15T04:47:41 Z akzytr Stove (JOI18_stove) C++17
50 / 100
 237 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
template <typename T> using ve = vector<T>;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define endl '\n'

int main() {

	int N, K;
	cin >> N >> K;

	ve<pair<int, int>> times(N);
	for(int i = 0; i < N; i++) {
		scanf("%d", &times[i].fi);
		times[i].se = 1;
	}
	for(int i = 0; i < N - 1; i++) {
		if(times[i + 1].fi != times[i].fi + 1) {
			times.push_back({times[i].fi + 1, 0});
		}
	}

	times.push_back({times[N - 1].fi + 1, 0});

	sort(times.begin(), times.end());

	int dp[times.size() + 2][K + 1];

	int mi_left[K + 1] = {};
	int mi_left2[K + 1] = {};

	bool tk = false;

	for(int i = 0; i <= K; i++) {
		mi_left[i] = 0;
		mi_left2[i] = (int)1e9;
	}

	for(int i = times.size() - 1; i >= 0; i--) {
		for(int left = K; left >= 0; left--) {
			tk = (tk || times[i].se);
			dp[i][left] = (!tk ? 0 : (int)1e9);
			mi_left2[left] = min(mi_left2[left], (tk == 0 ? 0 : (int)1e9) + times[i].fi);

			if(left == 0) {
				break;
			}
			if(times[i].se) {
				dp[i][left] = min(dp[i][left], mi_left2[left - 1] - times[i].fi);
				mi_left[left] = dp[i][left];
			} else {
				dp[i][left] = mi_left[left];

				mi_left2[left] = min(mi_left2[left], dp[i][left] + times[i].fi);
			}
		}
	}
	cout << dp[0][K] << endl;
}

/*
Subtask 1) N<=20 & Ti<=20

N * K * T greedy


DP[i][left][on] which means the stove is on on the i'th day

DP[i][left][off]
*/

Compilation message

stove.cpp: In function 'int main()':
stove.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &times[i].fi);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 4 ms 2640 KB Output is correct
12 Correct 29 ms 23888 KB Output is correct
13 Correct 53 ms 47432 KB Output is correct
14 Correct 78 ms 68628 KB Output is correct
15 Correct 79 ms 70728 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 4 ms 2640 KB Output is correct
12 Correct 29 ms 23888 KB Output is correct
13 Correct 53 ms 47432 KB Output is correct
14 Correct 78 ms 68628 KB Output is correct
15 Correct 79 ms 70728 KB Output is correct
16 Correct 34 ms 10452 KB Output is correct
17 Correct 113 ms 80960 KB Output is correct
18 Runtime error 237 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -