Submission #857786

#	Time	Username	Problem	Language	Result	Execution time	Memory
857786		TrinhKhanhDung	K blocks (IZhO14_blocks)	C++14	0 / 100	20 ms	161880 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) v.begin(),v.end()
#define v1 vector<ll>
#define v2 vector<vector<ll>>
#define MAX_M (int)20003
#define MOD (ll)(998244353)
#define INF (int)1e9
#define oo (ll)1e18

template <class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template <class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

using namespace std;

const int MAX = 1e5 + 3;
const int MAX_K = 1e2 + 3;

int N, K;
int a[MAX], L[MAX];
ll f[MAX_K][MAX], Min[MAX_K][MAX];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    for(int i=1; i<=N; i++){
        cin >> a[i];
    }

    stack<int> st;
    st.push(0);
    a[0] = INF;
    for(int i=1; i<=N; i++){
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        L[i] = st.top();
        st.push(i);
    }

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    memset(Min, 0x3f, sizeof Min);
    memset(Min[0], 0, sizeof Min[0]);

    for(int i=1; i<=K; i++){
        for(int j=i; j<=N; j++){
            if(L[j] >= i) minimize(f[i][j], f[i][L[j]]);
            if(L[j] >= i-1) minimize(f[i][j], f[i - 1][L[j]] + a[j]);
            else minimize(f[i][j], Min[i-1][j-1] + a[j]);
            Min[i][j] = min(Min[i][j-1], f[i][j]);
        }
    }

//    for(int i=1; i<=K; i++){
//        for(int j=1; j<=N; j++){
//            cout << f[i][j] << ' ';
//        }
//        cout << "\n\n";
//    }

    cout << f[K][N];

    return 0;
}

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