제출 #485346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485346		silverfox	K개의 묶음 (IZhO14_blocks)	C++14	53 / 100	1093 ms	5740 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

const long long maxn = 1e5;
const long long maxk = 1e2;

long long a[maxn+1];
long long f[maxn+1][maxk+1];

const long long oo = 1e16;

int main()
{
    long long n,k; cin >> n >> k;
    for (long long i = 1; i <= n; i++) {cin >> a[i];}

    /*for (long long i = 1; i <= k; i++)
    {
        if (i == 1) {f[1][i] = a[1];} else {f[1][i] = +oo;}
    }*/
    for (int i = 0; i <= k; i++)
    {
        f[0][i] = +oo;
    }

    long long totalMax = -1;
    for (long long i = 1; i <= n; i++)
    {
        totalMax = max(totalMax, a[i]);
        for (long long j = 1; j <= k; j++)
        {
            f[i][j] = +oo;
            if (j > i) {continue;}

            if (j == 1)
            {
                f[i][j] = totalMax; continue;
            }

            long long curMax = a[i];
            for (long long x = i-1; x >= 1; x--)
            {
                f[i][j] = min(f[i][j], f[x][j-1] + curMax);
                curMax = max(curMax, a[x]);
            }
        }
    }
    cout << f[n][k];
}

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