Submission #646293

#	Time	Username	Problem	Language	Result	Execution time	Memory
646293		ymm	K blocks (IZhO14_blocks)	C++17	53 / 100	1082 ms	9836 KiB

blocks

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'032;
const int K = 110;
const ll inf = 1e15;
ll dp[K][N];
ll a[N];
int n;

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
ll get_min(int k, int l, int r)
{
	ll ans = inf;
	Loop (i,l,r)
		ans = min(ans, dp[k][i]);
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int k;
	cin >> n >> k;
	Loop (i,0,n)
		cin >> a[i];
	dp[1][0] = a[0];
	Loop (i,2,k+1)
		dp[i][0] = inf;
	vector<int> vec;
	vec.push_back(0);
	Loop (i,1,n) {
		while (vec.size() && a[vec.back()] < a[i])
			vec.pop_back();
		dp[1][i] = max(a[i], dp[1][i-1]);
		Loop (j,2,k+1) {
			dp[j][i] = get_min(j-1, vec.size()?
			                        vec.back():
			                        0, i) + a[i];
			if (vec.size())
				dp[j][i] = min(dp[j][i], dp[j][vec.back()]);
		}
		vec.push_back(i);
	}	
	cout << dp[k][n-1] << '\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47