제출 #922509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922509		phong	K개의 묶음 (IZhO14_blocks)	C++17	0 / 100	35 ms	85340 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];
void ckmax(ll &a, ll b){
    a = max(a, b);
}
deque<int> de;
multiset<pii> mt[M];
int L[nmax][M];
int get(int i, int j){
    int u = L[i][j];
    if(f[u][j] > oo) ++u;
    if(u == i) --u;
    return u;
}
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){
        for(int j = 1; j <= k; ++j){
            auto &cur = L[i][j];
            cur = i - 1;
            while(cur > 0 && a[cur] <= a[i] && f[cur][j] < oo) cur = L[cur][j];
        }
        if(i == 1) continue;
        while(de.size() && a[de.back()] <= a[i]){
            int u = de.back();
            for(int j = 2; j <= min(k, i); ++j){
                int x = get(u, j - 1);
                mt[j].erase({f[x][j - 1] + a[u], u});
            }
            de.pop_back();
        }
        de.push_back(i);
        for(int j = 2; j <= min(k, i); ++j){
            int x = get(i, j - 1);
            mt[j].insert({f[x][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


*/

컴파일 시 표준 에러 (stderr) 메시지

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

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