Submission #1116972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116972		whoknow	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	2384 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define F first
#define S second
#define MAXN 100005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n, K;
int a[MAXN];
namespace sub1
{
ll dp[2][MAXN];
void solve()
{
    int mi = 1e9;
    for(int i = 1; i <= n; i++)
    {
        mi = min(mi, a[i]);
        dp[0][i] = mi;
    }
    for(int j = 2; j <= K; j++)
    {
        stack<ii>st;
        for(int i = 1; i <= n; i++)
        {
            while(sz(st) && st.top().S < a[i])
                st.pop();
            if(sz(st) == 0 || dp[0][i] + a[i] <= st.top().F + st.top().S)
                st.push({dp[0][i], a[i]});
            if(i > j)
                dp[1][i] = st.top().F + st.top().S;
        }
        for(int i = 1; i <= n; i++)
            dp[0][i] = dp[1][i];
    }
    cout<<dp[0][n];
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> K;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sub1::solve();
}

Compilation message (stderr)

blocks.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main()
      | ^~~~

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