제출 #102688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102688		stefdasca	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	343 ms	40328 KiB

blocks

/*
        IZhO 14-Blocks(same as this 2008 Romanian problem - https://www.infoarena.ro/problema/ksecv)

    We can solve it using deques, where dp[i][j] = min sum if we split the first j numbers in i sequences

*/
#include<bits/stdc++.h>
using namespace std;
int n, k, dp[102][100002], v[100002];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    int mx = 0;
    for(int i = 1; i <= n; ++i)
    {
        mx = max(mx, v[i]);
        dp[1][i] = mx;
    }
    for(int i = 2; i <= k; ++i)
    {
        deque<int>val;
        deque<int>pmax;
        deque<int>pmin;
        for(int j = i; j <= n; ++j)
        {
            int zmin = j-1;
            while(!val.empty() && v[j] >= v[val.back()])
            {
                if(dp[i-1][pmin.back()] < dp[i-1][zmin])
                    zmin = pmin.back();
                pmin.pop_back();
                val.pop_back();
                pmax.pop_back();
            }
            val.push_back(j);
            pmin.push_back(zmin);
            if(val.size() == 1)
                pmax.push_back(dp[i-1][zmin] + v[j]);
            else
            {
                if(pmax.back() < dp[i-1][zmin] + v[j])
                    pmax.push_back(pmax.back());
                else
                    pmax.push_back(dp[i-1][zmin] + v[j]);
            }
            dp[i][j] = pmax.back();
        }
    }
    cout << dp[k][n] << '\n';
    return 0;
}

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