제출 #1270619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270619		flaming_top1	Stove (JOI18_stove)	C++20	50 / 100	1096 ms	2788 KiB

stove

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 1e15;

using namespace std;

int n, k, mode;
lint a[100005], dp[2][100005];

void dnq(int l, int r, int optl, int optr)
{
    if (l > r)
        return;
    int mid = (l + r) >> 1, opt = optl;
    lint best = INF;
    int lim = min(optr, mid - 1);
    for (int t = optl; t <= lim; ++t)
    {
        lint val = dp[mode][t] + (a[mid] - a[t + 1] + 1);
        if (val < best)
        {
            best = val;
            opt = t;
        }
    }
    dp[mode ^ 1][mid] = best;
    dnq(l, mid - 1, optl, opt);
    dnq(mid + 1, r, opt, optr);
}

fami lore()
{
    SPED;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    if (k >= n)
    {
        cout << n << endl;
        return 0;
    }

    for (int i = 0; i <= n; ++i)
        dp[0][i] = (i == 0 ? 0 : INF);
    mode = 0;

    for (int j = 1; j <= k; ++j)
    {
        dp[mode ^ 1][0] = 0;
        dnq(1, n, 0, n - 1);
        mode ^= 1;
    }

    cout << dp[mode][n] << endl;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50