oj.uz

Submission #1100946

# Submission time Handle Problem Language Result Execution time Memory
1100946 2024-10-15T04:44:26 Z akzytr Stove (JOI18_stove) C++17
50 / 100
 234 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<ll, ll>> times(N);
	for(ll i = 0; i < N; i++) {
		scanf("%lld", &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, 0ll});
		}
	}

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

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

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

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

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

	bool tk = false;

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

	for(ll i = times.size() - 1; i >= 0; i--) {
		for(ll left = K; left >= 0; left--) {
			tk = (tk || occ[i]);
			dp[i][left] = (!tk ? 0 : (ll)1e16);
			mi_left2[left] = min(mi_left2[left], (tk == 0 ? 0 : (ll)1e16) + 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<long long int, long long int>, std::allocator<std::pair<long long int, long long 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("%lld", &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 1 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 1 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 848 KB Output is correct
11 Correct 6 ms 5200 KB Output is correct
12 Correct 65 ms 47444 KB Output is correct
13 Correct 113 ms 94472 KB Output is correct
14 Correct 146 ms 136776 KB Output is correct
15 Correct 148 ms 141132 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 1 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 848 KB Output is correct
11 Correct 6 ms 5200 KB Output is correct
12 Correct 65 ms 47444 KB Output is correct
13 Correct 113 ms 94472 KB Output is correct
14 Correct 146 ms 136776 KB Output is correct
15 Correct 148 ms 141132 KB Output is correct
16 Correct 42 ms 23216 KB Output is correct
17 Correct 187 ms 164024 KB Output is correct
18 Runtime error 234 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -