oj.uz

Submission #87268

# Submission time Handle Problem Language Result Execution time Memory
87268 2018-11-30T06:35:47 Z Yaroslaff K blocks (IZhO14_blocks) C++14
100 / 100
 196 ms 14684 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
//#define int ll
#define ld long double
#define null nullptr
#define endl '\n'

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int M = 1e9 + 7;
const int N = 1e5 + 7;

int n, k, x[N];
vector<int> res(N, M), curr;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#else
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
#endif
    cin >> n >> k;res[0] = 0;
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int j = 0; j < k; j++){
        vector<int> mx, dp;
        curr.assign(N, M);
        for (int i = 0; i < n; i++){
            int cur = res[i];
            while (!mx.empty() && mx.back() < x[i]){
                cur = min(cur, dp.back());
                mx.pop_back();
                dp.pop_back();
            }
            if (mx.empty() || cur + x[i] < dp.back() + mx.back())
                mx.pb(x[i]), dp.pb(cur);
            if (i >= j) curr[i + 1] = mx.back() + dp.back();
        }
        res = curr;
    }
    cout << res[n];
    return 0;
}

Compilation message

blocks.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1308 KB Output is correct
3 Correct 3 ms 1308 KB Output is correct
4 Correct 3 ms 1308 KB Output is correct
5 Correct 3 ms 1384 KB Output is correct
6 Correct 3 ms 1384 KB Output is correct
7 Correct 3 ms 1384 KB Output is correct
8 Correct 3 ms 1440 KB Output is correct
9 Correct 3 ms 1572 KB Output is correct
10 Correct 3 ms 1572 KB Output is correct
11 Correct 3 ms 1572 KB Output is correct
12 Correct 3 ms 1600 KB Output is correct
13 Correct 3 ms 1600 KB Output is correct
14 Correct 3 ms 1600 KB Output is correct
15 Correct 3 ms 1600 KB Output is correct
16 Correct 3 ms 1600 KB Output is correct
17 Correct 3 ms 1604 KB Output is correct
18 Correct 4 ms 1608 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 3 ms 1744 KB Output is correct
3 Correct 3 ms 1744 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct
5 Correct 3 ms 1752 KB Output is correct
6 Correct 3 ms 1756 KB Output is correct
7 Correct 3 ms 1760 KB Output is correct
8 Correct 3 ms 1764 KB Output is correct
9 Correct 3 ms 1768 KB Output is correct
10 Correct 3 ms 1808 KB Output is correct
11 Correct 3 ms 1808 KB Output is correct
12 Correct 3 ms 1808 KB Output is correct
13 Correct 3 ms 1808 KB Output is correct
14 Correct 4 ms 1868 KB Output is correct
15 Correct 3 ms 1868 KB Output is correct
16 Correct 4 ms 1868 KB Output is correct
17 Correct 4 ms 1868 KB Output is correct
18 Correct 3 ms 1884 KB Output is correct
19 Correct 4 ms 1884 KB Output is correct
20 Correct 4 ms 1884 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1944 KB Output is correct
2 Correct 3 ms 1944 KB Output is correct
3 Correct 3 ms 1944 KB Output is correct
4 Correct 3 ms 1944 KB Output is correct
5 Correct 3 ms 1944 KB Output is correct
6 Correct 3 ms 1944 KB Output is correct
7 Correct 3 ms 1944 KB Output is correct
8 Correct 3 ms 1944 KB Output is correct
9 Correct 3 ms 1944 KB Output is correct
10 Correct 3 ms 1944 KB Output is correct
11 Correct 3 ms 1948 KB Output is correct
12 Correct 3 ms 2028 KB Output is correct
13 Correct 5 ms 2028 KB Output is correct
14 Correct 5 ms 2028 KB Output is correct
15 Correct 12 ms 2028 KB Output is correct
16 Correct 12 ms 2028 KB Output is correct
17 Correct 7 ms 2028 KB Output is correct
18 Correct 12 ms 2028 KB Output is correct
19 Correct 11 ms 2028 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2108 KB Output is correct
2 Correct 8 ms 2564 KB Output is correct
3 Correct 12 ms 2804 KB Output is correct
4 Correct 43 ms 3220 KB Output is correct
5 Correct 114 ms 4040 KB Output is correct
6 Correct 16 ms 4780 KB Output is correct
7 Correct 56 ms 5408 KB Output is correct
8 Correct 5 ms 5408 KB Output is correct
9 Correct 7 ms 5408 KB Output is correct
10 Correct 7 ms 5408 KB Output is correct
11 Correct 7 ms 5408 KB Output is correct
12 Correct 3 ms 5408 KB Output is correct
13 Correct 4 ms 5408 KB Output is correct
14 Correct 22 ms 5408 KB Output is correct
15 Correct 4 ms 5408 KB Output is correct
16 Correct 8 ms 5408 KB Output is correct
17 Correct 8 ms 5868 KB Output is correct
18 Correct 10 ms 6280 KB Output is correct
19 Correct 44 ms 6464 KB Output is correct
20 Correct 103 ms 7276 KB Output is correct
21 Correct 17 ms 7952 KB Output is correct
22 Correct 54 ms 8664 KB Output is correct
23 Correct 14 ms 9304 KB Output is correct
24 Correct 22 ms 9988 KB Output is correct
25 Correct 110 ms 10672 KB Output is correct
26 Correct 3 ms 10672 KB Output is correct
27 Correct 4 ms 10672 KB Output is correct
28 Correct 37 ms 10672 KB Output is correct
29 Correct 6 ms 10672 KB Output is correct
30 Correct 10 ms 10672 KB Output is correct
31 Correct 9 ms 11080 KB Output is correct
32 Correct 20 ms 11652 KB Output is correct
33 Correct 77 ms 11992 KB Output is correct
34 Correct 196 ms 13428 KB Output is correct
35 Correct 17 ms 13700 KB Output is correct
36 Correct 85 ms 14684 KB Output is correct
37 Correct 4 ms 14684 KB Output is correct
38 Correct 21 ms 14684 KB Output is correct
39 Correct 4 ms 14684 KB Output is correct
40 Correct 4 ms 14684 KB Output is correct
41 Correct 3 ms 14684 KB Output is correct
42 Correct 3 ms 14684 KB Output is correct