Submission #281747

#	Time	Username	Problem	Language	Result	Execution time	Memory
281747		hieppgga	K blocks (IZhO14_blocks)	C++14	100 / 100	327 ms	41976 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
void readInput()
{

}
void solve()
{

}
int a[100004],n,k,lef[100004],minn[100004],maxx[100004],dp[104][100004];
int INF=2e8;
stack<int> s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    readInput();
    solve();
    cin>>n>>k;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=1; i<=n; i++)
    {
        minn[i]=INF;
        maxx[i]=INF;
    }
    s.push(1);
    int maxxx=0;
    for(int i=1; i<=n; i++)
    {
        maxxx=max(maxxx,a[i]);
        dp[1][i]=maxxx;
    }
    for(int i=2; i<=n; i++)
    {
        while(!s.empty())
        {
            if(a[s.top()]>a[i])
            {
                //  dp[1][i]=a[s.top()];
                lef[i]=s.top();
                int c=min(maxx[s.top()],min(minn[i],dp[1][i]));
                minn[i]=min(minn[i],min(dp[1][s.top()],maxx[s.top()]));
                maxx[s.top()]=c;
                break;
            }
            else
                minn[i]=min(min(minn[i],minn[s.top()]),min(dp[1][s.top()],maxx[s.top()])),s.pop();
        }
        s.push(i);
        //if(dp[1][i]==0) dp[1][i]=a[i];
    }
    dp[1][0]=INF;
    for(int i=2; i<=k; i++)
    {
        dp[i][0]=INF;
        for(int j=1; j<=n; j++)
        {
            dp[i][j]=dp[i][lef[j]];
            dp[i][j]=min(dp[i][j],minn[j]+a[j]);
            minn[j]=INF;
            maxx[j]=INF;
        }
        while(!s.empty())
            s.pop();
        s.push(1);
        for(int j=2; j<=n; j++)
        {
            while(!s.empty())
            {
                if(a[s.top()]>a[j])
                {
                    //  dp[1][i]=a[s.top()];
                    int c=min(maxx[s.top()],min(minn[j],dp[i][j]));
                    minn[j]=min(minn[j],min(dp[i][s.top()],maxx[s.top()]));
                    maxx[s.top()]=c;
                    break;
                }
                else
                    minn[j]=min(min(minn[j],minn[s.top()]),min(dp[i][s.top()],maxx[s.top()])),s.pop();
            }
            s.push(j);
            //if(dp[1][i]==0) dp[1][i]=a[i];
        }
    }
    cout<<dp[k][n];

}

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