Submission #1083743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083743		hh800295	K blocks (IZhO14_blocks)	C++17	53 / 100	44 ms	79496 KiB

blocks

#include<bits/stdc++.h>
#define int long long
#define forint(i,a,b) for (int i=a;i<=b;++i)
#define forinc(i,a,b) for (int i=a;i>=b;--i)
#define vt vector<int>
#define par pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+1;
const int K=101;
const int MOD=1e9+7;
int n,k;
int a[N];
int f[N][K];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    forint(i,1,n)
    {
        cin >> a[i];
    }
    memset(f,MOD,sizeof(f));
    f[1][0]=0;
    forint(i,1,n)
    {
        f[1][i]=max(f[1][i-1],a[i]);
    }
    forint(i,2,k)
    {
        stack <par> s;
        forint(j,i,n)
        {
            int mi=f[i-1][j-1];
            while(!s.empty()&&a[s.top().se]<=a[j])
            {
                mi=min(mi,s.top().fi);
                s.pop();
            }
            f[i][j]=min(f[i][s.empty() ? 0 : s.top().se],mi+a[j]);
            s.push({mi,j});
        }
    }
    cout << f[k][n];
    return 0;
}

Compilation message (stderr)

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

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