oj.uz

Submission #1100947

# Submission time Handle Problem Language Result Execution time Memory
1100947 2024-10-15T04:46:11 Z akzytr Stove (JOI18_stove) C++17
50 / 100
 268 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());

	ve<int> occ(times.size(), 0);
	for(int i = 0; i < times.size(); i++) {
		occ[i] = times[i].se;
	}

	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 || occ[i]);
			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(occ[i]) {
				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:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < times.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 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 31 ms 23888 KB Output is correct
13 Correct 56 ms 47432 KB Output is correct
14 Correct 85 ms 68424 KB Output is correct
15 Correct 99 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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 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 31 ms 23888 KB Output is correct
13 Correct 56 ms 47432 KB Output is correct
14 Correct 85 ms 68424 KB Output is correct
15 Correct 99 ms 70728 KB Output is correct
16 Correct 37 ms 11212 KB Output is correct
17 Correct 123 ms 81728 KB Output is correct
18 Runtime error 268 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -