oj.uz

Submission #253564

# Submission time Handle Problem Language Result Execution time Memory
253564 2020-07-28T10:03:45 Z index_ K blocks (IZhO14_blocks) C++17
0 / 100
 3 ms 1024 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <chrono>
#include <cassert>
#include <bitset>
#include <random>

using namespace std;

typedef long long li;
typedef  long double ld;
const li MAX = 3e5 + 20;

li inf = (li)1e15;
li mod = (li)998244353;

li dp1[MAX], dp2[MAX], p[MAX], cool[MAX];
li n, k, a[MAX];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<li> cur;
    for (int i = 1; i <= n; i++) {
        while (cur.size() && cur.back() < a[i]) cur.pop_back();
        if (cur.size()) p[i] = cur.back();
        cur.push_back(a[i]);
    }
    li cur_max = a[1];
    dp1[0] = inf;
    dp2[0] = inf;
    for (int i = 1; i <= n; i++) {
        cur_max = max(cur_max, a[i]);
        dp1[i] = cur_max;
    }

    for (int j = 2; j <= k; j++) {
        for (int i = 1; i <= n; i++) {
            cool[i] = 0;
            if (dp1[p[i]] == inf) cool[i] = 1;
            else dp2[i] = dp1[p[i]];
        }
        li cur_min = dp1[j - 1];
        for (int i = j; i <= n; i++) {
            if (cool[i]) dp2[i] = cur_min + a[i];
            cur_min = min(cur_min, dp1[i]);
        }

        for (int i = 1; i <= n; i++) {
            dp1[i] = dp2[i];
            dp2[i] = 0;
        }
    }

    cout << dp1[n];
}

int main() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios::sync_with_stdio(0);
    li q;
    q = 1;
    while (q--) solve();

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -