oj.uz

Submission #856768

# Submission time Handle Problem Language Result Execution time Memory
856768 2023-10-04T13:46:14 Z ilovveyyou K blocks (IZhO14_blocks) C++14
53 / 100
 91 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define left _left
#define right _right
#define ll long long
#define sz(s) ((int)(s).size())
#define ALL(v) (v).begin(), (v).end()

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define FOREACH(x, a) for (auto x : (a))

#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1LL)
#define popcount __builtin_popcountll

template<class T1, class T2> inline bool maximize(T1 &x, T2 y) {
    T1 EPS = 1e-9;
    if (x + EPS < y) return x = y, true;
    return false;
}
template<class T1, class T2> inline bool minimize(T1 &x, T2 y) {
    T1 EPS = 1e-9;
    if (x > y + EPS) return x = y, true;
    return false;
}
template<class T> inline vector<T> remove_duplicate(vector<T> a) {
    sort(ALL(a)); a.resize(unique(ALL(a))-a.begin());
    return a;
}

#define TASK "elecar"
void online() {
    freopen(TASK".inp", "r", stdin);
    freopen(TASK".out", "w", stdout);
}
const ll oo = 4e18 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

const int MAX = (int) 1e5 + 5;

int n, k;
ll a[MAX];

namespace sub_one {

    void perform() {
        #define Fast vector<vector<ll>>
        Fast dp(n+1, vector<ll>(k+1, oo));
        Fast max_cost(n+1, vector<ll>(n+1, 0));

        FOR(i, 1, n) FOR(j, i, n) {
            if (i == j)
                max_cost[i][j] = a[j];
            else max_cost[i][j] = max(max_cost[i][j-1], a[j]);
        }

        dp[0][0] = 0;

        FOR(i, 1, n) FOR(j, 1, k) {
            FOR(r, 0, i-1) {
                minimize(dp[i][j], dp[r][j-1] + max_cost[r+1][i]);
            }
        }

        cout << dp[n][k] << "\n";
    }
}

signed main(void) {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];

    #define CHECK 25000000
    if (n * k <= CHECK)
        return sub_one::perform(), 0;

    return 0;
}

Compilation message

blocks.cpp: In function 'void online()':
blocks.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen(TASK".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen(TASK".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 464 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 352 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 464 KB Output is correct
50 Correct 0 ms 464 KB Output is correct
51 Correct 1 ms 532 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 468 KB Output is correct
54 Correct 1 ms 604 KB Output is correct
55 Correct 1 ms 604 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 604 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 464 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 352 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 464 KB Output is correct
50 Correct 0 ms 464 KB Output is correct
51 Correct 1 ms 532 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 468 KB Output is correct
54 Correct 1 ms 604 KB Output is correct
55 Correct 1 ms 604 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Runtime error 91 ms 262144 KB Execution killed with signal 9
59 Halted 0 ms 0 KB -