Submission #1173654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173654		MPG	K blocks (IZhO14_blocks)	C++20	100 / 100	141 ms	4288 KiB

blocks

//#pragma GCC optomize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define     max_heap priority_queue<pair <ll, pair <ll, ll>>>
//#define     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define     min_heap priority_queue<pair <ll, pair <ll, ll>>, vector<pair <ll, pair <ll, ll>>>, greater<pair <ll, pair <ll, ll>>>>

#define     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define     filE freopen("in.txt", "r", stdin);// freopen("out1.txt", "w", stdout); 
#define     endl '\n'
#define     md(a) (a % mod + mod) % mod
#define     pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769


ll const maxn = 2e5 + 123;
ll const inf = 3e18;
ll const loG = 18; // 23
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}



ll n, k, arr[maxn], dp[maxn][2];

vector <pair <ll, pair <ll, ll>>> stk;



void Solve(){

cin >> n >> k;


for (int i = 1; i < n + 1; i++)
    cin >> arr[i];

for (int i = 1; i < n + 1; i++){
    dp[i][0] = max(dp[i - 1][0], arr[i]);
    dp[i][1] = inf;
}
dp[0][1] = inf;
dp[0][0] = inf;

for (int j = 2; j < k + 1; j++){
    stk.clear();
    for (int i = 1; i < n + 1; i++){
        ll pd = dp[i - 1][0];
        while (stk.size() && stk.back().first <= arr[i]){ 
            pd = min(pd, stk.back().second.first);
            stk.pop_back();
        }
        if (stk.size())
            dp[i][1] = min(dp[i][1], stk.back().second.second);
        dp[i][1] = min(dp[i][1], pd + arr[i]);
        stk.pb({arr[i], {pd, dp[i][1]}});
        //cout << i << ' ' << pd << " " << dp[i][1] << endl;
    }

    for (int i = 1; i < n + 1; i++){
        dp[i][0] = dp[i][1];
        dp[i][1] = inf;
    }
}
cout << dp[n][0] << endl;

}



int main(){
sariE;
//filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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