oj.uz

Submission #647609

# Submission time Handle Problem Language Result Execution time Memory
647609 2022-10-03T10:00:02 Z dattranxxx K blocks (IZhO14_blocks) C++11
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 5;
const ll inf = 1e18;
int a[N];

int n, m;

vector<ll> pre, cur;
#define fi first
#define se second

void solve(int l, int r, int x, int y) {
	if (l > r) return;
	int m = l + r >> 1;
	pair<ll, int> best = {inf, -1};
	
	for (int i = min(m, y), val = a[i]; i >= x; --i, val = max(val, a[i]))
		best = min(best, {pre[i - 1] + val, i});
	cur[m] = best.fi;
	solve(l, m - 1, x, best.se);
	solve(m + 1, r, best.se, y);
}

void task1() {
	for (int k = 1; k <= m; ++k) {
		for (int i = 1; i <= n; ++i) {
			cur[i] = inf;
			for (int j = i, val = a[i]; j; --j, val = max(val, a[j])) {
				cur[i] = min(cur[i], pre[j - 1] + val);
			}
		}
		cur.swap(pre);
	}
	cout << pre[n];
}

int main() {
	if (fopen("kblocks.inp", "r"))
		freopen("kblocks.inp", "r", stdin),
		freopen("kblocks.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	pre.assign(n + 1, inf); cur.assign(n + 1, inf);
	pre[0] = 0;
	
	//if (n <= 100) return task1(), 0;
	
	for (int k = 1; k <= m; ++k) {
		stack<pair<int, ll>> st;
		for (int i = 1; i <= n; ++i) {
			ll val = pre[i - 1];
			while (!st.empty() && a[i] > a[st.top().fi]) {
				val = min(val, st.top().se); st.pop();
			}
			cur[i] = val + a[i];
			st.emplace(i, val);
		}
		cur.swap(pre);
	}
	cout << pre[n];
	return 0;
}

Compilation message

blocks.cpp: In function 'void solve(int, int, int, int)':
blocks.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |  int m = l + r >> 1;
      |          ~~^~~
blocks.cpp: In function 'int main()':
blocks.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   freopen("kblocks.inp", "r", stdin),
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:43:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   freopen("kblocks.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 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 212 KB Output is correct
2 Incorrect 1 ms 212 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 212 KB Output is correct
2 Incorrect 0 ms 212 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 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -