Submission #1176805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176805		_hyg_	K개의 묶음 (IZhO14_blocks)	C++20	0 / 100	45 ms	82504 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) {if (__a > __b) {__a = __b; return true;} return false;}
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) {if (__a < __b) {__a = __b; return true;} return false;}

#define sp ' '
#define el '\n'
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define int long long
#define _HyG_ signed main()
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x>>i)&1)
#define SON(x, i) ((x) | MASK(i))
#define SOF(x, i) ((x) & ~MASK(i))
#define BIT_C(x) __builtin_popcountll(x)
#define fu(i,a,b) for(int i = a; i <= b; i++)
#define fd(i,a,b) for(int i = a; i >=b ; i--)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define file(name) freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);

const int N = 1e5 + 5;
const int Log = 20;
const int MOD = 1e9 + 7;
const ll oo = 4485090715960753727;
const int base = 301;
const int so = (int)2e5;

int n, k, a[N], f[N][105];

void init()
{
    cin>>n>>k;
    fu(i, 1, n) cin>>a[i];
}

vector<vector<int>> Tree;
int MaxTree;

void update(int kk, int id, int l, int r, int pos, int vl)
{
    if (pos > r && pos < l) return;
    if (l == r)
    {
        Tree[id][kk] = min(Tree[id][kk], vl);
        return;
    }
    else
    {
        int m =(l + r)/2;
        update(kk, id * 2, l, m, pos, vl);
        update(kk, id * 2 + 1, m + 1, r, pos, vl);
        Tree[id][kk] = min(Tree[id * 2][kk], Tree[id * 2 + 1][kk]);
    }
}

int query(int kk, int id, int l, int r, int u, int v)
{
    if (r < u || l > v) return oo;
    if (l >= u && r <= v) return Tree[id][kk];
    else
    {
        int m = (l + r)/2;
        int L = query(kk, id * 2, l, m, u, v);
        int R = query(kk, id * 2 + 1, m + 1, r, u, v);
        return min(L, R);
    }
}

void process()
{
    MaxTree = n;
    Tree.resize(4 * MaxTree + 1);
    fu(i, 0, 4 * MaxTree)
    {
        Tree[i].resize(k + 1);
        fill(Tree[i].begin(), Tree[i].end(), oo);
    }
    memset(f, 0x3f, sizeof f);
    stack<int> st;
    f[0][1] = 0;
    fu(i, 1, n)
    {
        while (st.size() && a[i] > a[st.top()]) st.pop();
        fu(j, 1, k)
        {
            int l = 1;
            if (st.size())
            {
                l = st.top();
                f[i][j] = min(f[i][j], f[st.top()][j]);
            }
            if (j == 1)
            {
                f[i][j] = max(f[i - 1][j], a[i]);
            }
            else
            {
                int vl = query(j - 1, 1, 1, MaxTree, l, i - 1);
                f[i][j] = min(f[i][j], vl + a[i]);
            }
            update(j, 1, 1, MaxTree, i, f[i][j]);
        }
        st.push(i);
    }
    cout<<f[n][k];
}

_HyG_
{
    fast
    //file("TREE");
    int t = 1; //cin>>t;
    while (t--)
    {
        init();
        process();
    }
    return (0^0);
}

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