제출 #647611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647611		dattranxxx	K개의 묶음 (IZhO14_blocks)	C++11	100 / 100	202 ms	3004 KiB

blocks

#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;
		cur.assign(n + 1, inf);
		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] = min(cur[st.empty() ? 0 : st.top().fi], val + a[i]);
			st.emplace(i, val);
		}
		cur.swap(pre);
	}
	cout << pre[n];
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47