Submission #922570

#	Time	Username	Problem	Language	Result	Execution time	Memory
922570		phong	K blocks (IZhO14_blocks)	C++17	100 / 100	355 ms	168408 KiB

blocks

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e5 + 5;
const ll oo = 1e18, base = 311;
const int lg = 19, M = 105;
const ll mod = 1e9 + 7;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

int n, k;
ll f[nmax][M], a[nmax], mi[nmax][M], h[nmax], b[nmax];
void ckmax(ll &a, ll b){
    a = max(a, b);
}
void ckmin(ll &a, ll b){
    a = min(a, b);
}
deque<int> de;
multiset<pii> mt;
int L[nmax];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> k;
    memset(f, 0x3f, sizeof f);
    memset(mi, 0x3f, sizeof f);

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        if(i == 1) f[1][1] = a[i];
        else f[i][1] = max(f[i - 1][1], a[i]);
    }
    h[0] = oo;
    for(int j = 1; j <= k; ++j){
        de.clear();mt.clear();
        for(int i = 1; i <= n; ++i){
            b[i] = mi[i][j - 1] + a[i];
        }
        for(int i = 1; i <= n; ++i){
            if(j > 1){
                while(de.size() && a[de.back()] <= a[i]){
                    h[de.size()] = oo;
                    de.pop_back();
                }
                int x = de.size();
                h[x + 1] = min(h[x], b[i]);
                de.push_back(i);
                f[i][j] = h[de.size()];
            }
            L[i] = i - 1;
            mi[i][j] = f[i - 1][j];
            while(L[i] && a[L[i]] <= a[i]){
                ckmin(mi[i][j],mi[L[i]][j]);
                L[i] = L[L[i]];
            }
        }
    }
    cout << f[n][k];

}
/*
5 2
1 2 3 4 5


*/

Compilation message (stderr)

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

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