Submission #1247906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247906		_dtq_	K blocks (IZhO14_blocks)	C++20	0 / 100	0 ms	328 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz(x) (ll)(x.size())
#define all(v) v.begin(), v.end()
#define sz(x) (ll)(x.size())
#define se second
#define fi first
using namespace std;

const ll N = 1e5 + 9;

const ll M = 109;

ll n, i, j, k, bit[M][N], dp[N][M], a[N];

void up( ll x, ll y, ll val )
{
    while(y <= n)
    {
        bit[x][y] = min(bit[x][y], val);

        y += (y & (-y));
    }
}

ll get( ll x, ll y )
{
    if(x == 0) return 1e18;

    ll maxn = 1e18;

    while(y > 0)
    {
        maxn = min(maxn, bit[x][y]);
        y -= (y & (-y));
    }

    return maxn;

}

int main()
{
#define TN "blocks"
    if(fopen(TN ".in", "r"))
    {
        freopen(TN ".inp", "r", stdin);
        freopen(TN ".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k;

    for( i = 1; i <= n; i ++ )
        cin >> a[i];

    stack<ll>f;

    for( i = 1; i <= n; i ++ )
        for( int j = 1; j <= k; j ++ ) bit[j][i] = 1e18;

    for( i = 1; i <= n; i ++ )
    {
        ll vt = 0;

        while(sz(f) && a[f.top()] <= a[i])
            f.pop();

        if(sz(f)) vt = f.top();

        if(vt == 0)
        {
            for( int w = 1; w <= min(i, k); w ++)
            {
                if(w == 1) dp[i][w] = a[i];
                else
                    dp[i][w] = a[i] + get(w - 1, n);
            }
        }
        else
        {
            for( int w = 1; w <= min(i, k); w ++ )
                dp[i][w] = min(dp[vt][w], a[i] + get(w - 1, n - vt));
        }

        f.push(i);

        for( int w = 1; w <= min(i, k); w ++ ) up(w, n - i + 1, dp[i][w]);
    }

    cout << dp[n][k];

    return 0;
}
/*
*/

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(TN ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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