oj.uz

Submission #857786

# Submission time Handle Problem Language Result Execution time Memory
857786 2023-10-07T00:55:38 Z TrinhKhanhDung K blocks (IZhO14_blocks) C++14
0 / 100
 20 ms 161880 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 161628 KB Output is correct
2 Correct 18 ms 161880 KB Output is correct
3 Correct 17 ms 161616 KB Output is correct
4 Correct 18 ms 161620 KB Output is correct
5 Correct 18 ms 161620 KB Output is correct
6 Correct 18 ms 161624 KB Output is correct
7 Correct 18 ms 161624 KB Output is correct
8 Correct 18 ms 161628 KB Output is correct
9 Incorrect 18 ms 161620 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 161632 KB Output is correct
2 Correct 19 ms 161628 KB Output is correct
3 Correct 18 ms 161480 KB Output is correct
4 Correct 18 ms 161628 KB Output is correct
5 Correct 18 ms 161640 KB Output is correct
6 Correct 20 ms 161876 KB Output is correct
7 Correct 18 ms 161560 KB Output is correct
8 Correct 19 ms 161616 KB Output is correct
9 Incorrect 18 ms 161628 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 161628 KB Output is correct
2 Correct 18 ms 161880 KB Output is correct
3 Correct 17 ms 161616 KB Output is correct
4 Correct 18 ms 161620 KB Output is correct
5 Correct 18 ms 161620 KB Output is correct
6 Correct 18 ms 161624 KB Output is correct
7 Correct 18 ms 161624 KB Output is correct
8 Correct 18 ms 161628 KB Output is correct
9 Incorrect 18 ms 161620 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 161628 KB Output is correct
2 Correct 18 ms 161880 KB Output is correct
3 Correct 17 ms 161616 KB Output is correct
4 Correct 18 ms 161620 KB Output is correct
5 Correct 18 ms 161620 KB Output is correct
6 Correct 18 ms 161624 KB Output is correct
7 Correct 18 ms 161624 KB Output is correct
8 Correct 18 ms 161628 KB Output is correct
9 Incorrect 18 ms 161620 KB Output isn't correct
10 Halted 0 ms 0 KB -