Submission #405165

#	Time	Username	Problem	Language	Result	Execution time	Memory
405165		MarcosPauloEvers	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	204 KiB

blocks

#include <bits/stdc++.h>

#define mid(l,r) ((l + r) >> 1)
#define lsb(x) (x & (-x))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define FOR(X,L,R) for(int X=L;X<R;++X)
#define endl '\n'
#define int long long
#define MOD ((int)1e9 + 7)
#define INF (0x3f3f3f3f)
#define LLINF (0x3f3f3f3f3f3f3f3fLL)

using namespace std;

template<typename T>
inline void input(vector<T>& v)
{
    for(T& x: v)
        cin >> x;
}

#define pow2(x) (1LL << (x))

class SparceTable
{
private:
    vector< vector<int> > sparce;
    vector<int> log;
    int n, m; // m = ceil(log2(n))
public:
    SparceTable(const vector<int>& v)
    {
        n = v.size();
        m = 1;
        while(pow2(m + 1) <= n) m++;

        sparce.assign(n, vector<int>(m, -LLINF));

        for(int i = 0; i < n; i++)
            sparce[i][0] = v[i];
        
        for(int j = 1; j <= m; j++)
        {
            for(int i = 0; i + pow2(j) <= n; i++)
            {
                sparce[i][j] = max(sparce[i][j - 1], sparce[i + pow2(j - 1)][j - 1]);
            }
        }

        log.assign(n + 1, 0);
        
        log[1] = 0;
        for(int i = 2; i <= n; i++)
        {
            log[i] = 1 + log[i / 2];
        }
    }
    int get_max(int i, int j)
    {
        int k = log[j - i + 1];
        return max(sparce[i][k], sparce[j - pow2(k) + 1][k]);
    }
};

void compute(
    array<vector<int>, 2>& dp,
    int curr_dp,
    SparceTable max_st,
    int l,
    int r,
    int optl,
    int optr
)
{
    if(l > r)
    {
        return;
    }
    int m = mid(l, r);
    pair<int, int> best = {LLINF, -1};

    for(int k = optl; k < min(m, optr); k++)
    {
        best = min(best, {dp[1 - curr_dp][k] + max_st.get_max(k + 1, m), k});
    }

    dp[curr_dp][m] = best.first;
    int opt = best.second;

    compute(dp, curr_dp, max_st,   l, m-1, optl,  opt+1);
    compute(dp, curr_dp, max_st, m+1,   r,  opt, optr);
}

void solve()
{
    int n, k; cin >> n >> k;
    vector<int> v(n); input(v);

    SparceTable sparce(v);

    array< vector<int>, 2> dp;
    dp[0] = vector<int>(n, LLINF);
    dp[1] = vector<int>(n, LLINF);

    int curr_dp = 0;

    dp[curr_dp][0] = v[0];
    for(int i = 1; i < n; i++)
    {
        dp[curr_dp][i] = max(dp[curr_dp][i - 1], v[i]);
    }

    curr_dp = 1 - curr_dp;

    for(int i = 2; i <= k; i++)
    {
        compute(dp, curr_dp, sparce, 0, n - 1, 0, n);

        curr_dp = 1 - curr_dp;
    }

    cout << dp[1-curr_dp][n - 1] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    #if defined(CODEFORCES) || defined(CF)
        int t; cin >> t;
        while(t--) solve();
    #else
        solve();
    #endif

    return 0;
}

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