Submission #1285483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285483		Faisal_Saqib	K blocks (IZhO14_blocks)	C++20	100 / 100	136 ms	4764 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100100;
ll a[N];
ll dp[N][3];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    dp[0][0]=dp[0][1]=1e14;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i][0]=1e14;
        dp[i][1]=a[i];
        if(i>1)dp[i][1]=max(dp[i-1][1],a[i]);
    }
    for(int j=2;j<=k;j++)
    {
        int p=j%2;
        for(int i=0;i<=n;i++)dp[i][p]=1e14;
        vector<int> st_mx;
        vector<ll> ans;
        for(int i=1;i<=n;i++)
        {
            // dp[i][p]=min( dp[i'][1-p] + max(a[i'+1 , i'+2 , .. , i]) ) 'i<i
            ll mi=dp[i-1][1-p]; // we always take this
            while(st_mx.size()>0 and a[st_mx.back()]<a[i])
            {
                st_mx.pop_back();
                mi=min(mi,ans.back());
                ans.pop_back();
            }
            if(st_mx.size()==0 or a[st_mx.back()]+ans.back()>a[i]+mi)
            {
                st_mx.push_back(i);
                ans.push_back(mi);
            }
            if(i>=j)
            {
                dp[i][p]=a[st_mx.back()]+ans.back();
            }
        }
    }
    cout<<dp[n][k%2]<<endl;
}

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