oj.uz

Submission #515798

# Submission time Handle Problem Language Result Execution time Memory
515798 2022-01-19T17:52:45 Z thiago_bastos K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 316 KB 
#include "bits/stdc++.h"

using namespace std;
 
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const i64 INF = 1e15L;

void solve() {
	
	int n, k;

	cin >> n >> k;

	vector<int> a(n + 1);
	vector<i64> dp(n + 1, INF);

	a[0] = 1e9;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	
	dp[0] = 0;

	for(int i = 1; i <= k; ++i) {
		vector<int> c;
		vector<i64> cost, pre, val(n + 1, INF);
		
		c.push_back(0);
		cost.push_back(INF);
		cost.push_back(dp[0]);
		pre.push_back(dp[0]);

		for(int j = 1; j <= n; ++j) {
			i64 x = dp[j - 1];			
			while(!c.empty() && c.back() < a[j]) {
				x = min(x, cost.back());
				c.pop_back();
				pre.pop_back();
				cost.pop_back();
			}
			c.push_back(a[j]);
			pre.push_back(min(cost.back(), x + a[j]));
			cost.push_back(x);		
			val[j] = pre.back();	
		}

		swap(dp, val);
	}

	cout << dp.back() << '\n';
}
 
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -