Submission #1094182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094182		MODDI	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	464 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define mp make_pair
int n, k;
vector<ll> arr;
ll dp[100100][110];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    arr.resize(n);
    for(int i = 0; i < n; i++)  cin >> arr[i];
    for(int i = 0; i < n; i++)  for(int j = 0; j < 101; j++)    dp[i][j] = 1e18;

    dp[0][1] = arr[0];
    for(int i = 1; i < n; i++){
        dp[i][1] = max(dp[i-1][1], arr[i]);
    }
    for(int splits = 2; splits <= k; splits++){
        stack<pair<int, ll> > st;
        for(int i = 0; i < n; i++){
            ll here = dp[i][splits-1];
            while(st.size() && st.top().first <= arr[i]){
                here = min(here, st.top().second);
                st.pop();
            }
            if(!st.size() || st.top().first + st.top().second > here + arr[i]){
                st.push({arr[i], here});
            }
            dp[i][splits] = st.top().first + st.top().second;
        }
    }
    cout<<dp[n-1][k]<<"\n";
}

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