#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn = 1e5 + 5; int a[maxn], f[maxn][105]; int N, K; signed main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("A.INP", "r")){ freopen("A.INP", "r", stdin); freopen("A.OUT", "w", stdout); } cin >> N >> K; fill_n(&f[0][0], maxn * 105, 1e9 + 5); int mx = 0; for (int i = 1; i <= N; ++i){ cin >> a[i]; mx = max(mx, a[i]); f[i][1] = mx; } for (int j = 2; j <= K; ++j){ vector<pair<pair<int, int>, int>> vec; for (int i = 1; i <= N; ++i){ int v = f[i - 1][j - 1]; while (vec.size() && vec.back().fi.fi <= a[i]){ v = min(v, vec.back().fi.se); vec.pop_back(); } int val = v + a[i]; if (vec.size()){ val = min(val, vec.back().se); } f[i][j] = val; vec.pb(mp(mp(a[i], v), val)); } } cout << f[N][K]; }

blocks.cpp: In function 'int main()':
blocks.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
blocks.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~