Submission #922500

#	Time	Username	Problem	Language	Result	Execution time	Memory
922500		phong	K blocks (IZhO14_blocks)	C++17	0 / 100	10 ms	42328 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, f[nmax][M], a[nmax];
void ckmax(int &a, int b){
    a = max(a, b);
}
deque<int> de;
multiset<pii> mt[M];
int L[nmax];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.ans", "w", stdout);
    cin >> n >> k;
    memset(f, 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]);
    }
    for(int i = 1; i <= n; ++i){
        L[i] = i - 1;
        while(L[i] > 0 && a[L[i]] <= a[i]) L[i] = L[L[i]];
    }
    for(int i = 2; i <= n; ++i){
        L[i] = max(L[i], 1);
        while(de.size() && a[de.back()] <= a[i]){
            int u = de.back();
            for(int j = 2; j <= min(k, i); ++j){
                mt[j].erase({f[L[u]][j - 1] + a[u], u});
            }
            de.pop_back();
        }
        de.push_back(i);
//        for(auto p : de) cout << p << ' ';
//        cout << "\n";
        for(int j = 2; j <= min(k, i); ++j){
            mt[j].insert({f[L[i]][j - 1] + a[i], i});
            auto it = *mt[j].begin();
            f[i][j] = it.fi;
        }
    }
    cout << f[n][k];
}
/*
5 3 2
2 3 3
3 5 5
5 1 6
5 4 3


*/

Compilation message (stderr)

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

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