oj.uz

Submission #857468

# Submission time Handle Problem Language Result Execution time Memory
857468 2023-10-06T09:01:22 Z TrinhKhanhDung K blocks (IZhO14_blocks) C++14
0 / 100
 10 ms 81244 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], R[MAX];
ll f[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;
    for(int i=1; i<=K; i++){
        for(int j=i; j<=N; j++){
            if(L[j] < i) f[i][j] = f[i-1][i-1] + a[j];
            else f[i][j] = f[i][L[j]];
        }
    }

    cout << f[K][N];

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 80984 KB Output is correct
2 Correct 10 ms 80988 KB Output is correct
3 Correct 10 ms 80988 KB Output is correct
4 Correct 9 ms 81068 KB Output is correct
5 Correct 9 ms 80872 KB Output is correct
6 Correct 10 ms 80988 KB Output is correct
7 Correct 9 ms 80988 KB Output is correct
8 Incorrect 9 ms 80988 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 80988 KB Output is correct
2 Correct 10 ms 80988 KB Output is correct
3 Correct 9 ms 81048 KB Output is correct
4 Correct 10 ms 80988 KB Output is correct
5 Correct 9 ms 80988 KB Output is correct
6 Correct 9 ms 80856 KB Output is correct
7 Correct 10 ms 81244 KB Output is correct
8 Incorrect 9 ms 80988 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 80984 KB Output is correct
2 Correct 10 ms 80988 KB Output is correct
3 Correct 10 ms 80988 KB Output is correct
4 Correct 9 ms 81068 KB Output is correct
5 Correct 9 ms 80872 KB Output is correct
6 Correct 10 ms 80988 KB Output is correct
7 Correct 9 ms 80988 KB Output is correct
8 Incorrect 9 ms 80988 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 80984 KB Output is correct
2 Correct 10 ms 80988 KB Output is correct
3 Correct 10 ms 80988 KB Output is correct
4 Correct 9 ms 81068 KB Output is correct
5 Correct 9 ms 80872 KB Output is correct
6 Correct 10 ms 80988 KB Output is correct
7 Correct 9 ms 80988 KB Output is correct
8 Incorrect 9 ms 80988 KB Output isn't correct
9 Halted 0 ms 0 KB -