Submission #1075011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075011		sitablechair	K blocks (IZhO14_blocks)	C++17	53 / 100	1027 ms	106652 KiB

blocks

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=1e5+3;
const ll INF=1e17;

int n,k,a[N],l[N],r[N];
ll f[N][104],stb[N][20];
stack<int> skull;
vector<ll> in[N],out[N];
multiset<ll> st;

void pre(int k) {
    For(i,1,n) stb[i][0]=f[i][k];
    for(int j=1;j<=16;j++)
        for(int i=1;i+(1<<j)-1<=n;i++) stb[i][j]=min(stb[i][j-1],stb[i+(1<<j-1)][j-1]);
}
int get(int l,int r) {
    int len=__lg(r-l+1);
    return min(stb[l][len],stb[r-(1<<len)+1][len]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    For(i,1,n) cin >> a[i];
    fill(l,l+n+1,-1);
    fill(r,r+n+1,n+1);
    For(i,1,n) {
        while(sz(skull) && a[skull.top()]<a[i]) {
            r[skull.top()]=i;
            skull.pop();
        }
        skull.push(i);
    }
    while(sz(skull)) skull.pop();
    ForD(i,n,1) {
        while(sz(skull) && a[skull.top()]<a[i]) {
            l[skull.top()]=i;
            skull.pop();
        }
        skull.push(i);
    }
    For(i,1,n) l[i]++,r[i]--;
    For(i,0,n)
        For(j,1,k) f[i][j]=INF;
    // Từ l[i]->i
    f[1][1]=a[1];
    For(i,2,n) f[i][1]=max(1LL*a[i],f[i-1][1]);
    For(j,2,k) {
        st.clear();
        pre(j-1);
        For(i,1,n) in[i].clear(),out[i].clear();
        For(i,j,n) {
            for(auto el: in[i]) st.insert(el);
            for(auto el: out[i]) st.erase(st.find(el));
            ll cur=get(max(l[i]-1,j-1),i-1)+a[i];
            f[i][j]=min(f[i][j],cur);
            if (sz(st)) f[i][j]=min(f[i][j],*st.begin());
            if (r[i]>i) {
                in[i+1].pb(cur);
                out[r[i]+1].pb(cur);
            }
            // For(k,j,i) f[i][j]=min(f[i][j],f[k-1][j-1]+get(k,i));
        }
    }
    cout << f[n][k];
    return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'void pre(int)':
blocks.cpp:40:77: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |         for(int i=1;i+(1<<j)-1<=n;i++) stb[i][j]=min(stb[i][j-1],stb[i+(1<<j-1)][j-1]);
      |                                                                            ~^~

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