oj.uz

Submission #470838

# Submission time Handle Problem Language Result Execution time Memory
470838 2021-09-05T23:37:20 Z jalsol Stove (JOI18_stove) C++17
50 / 100
 446 ms 199220 KB 
// looking to shine brighter in this world...

#define TASK "stove"

#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    cout << setprecision(12) << fixed;
    return true;
}();

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// ================================================================================

constexpr int maxn = 5000 + 5;

int n, k;
int a[maxn];
int dp[maxn][maxn];

int go(int i, int rem) {
    if (i == 0) return 0;
    if (rem <= 0) return inf;

    int& ret = dp[i][rem];
    if (ret != -1) return ret;

    ret = go(i - 1, rem) + a[i] - a[i - 1];
    if (rem > 0) {
        chmin(ret, go(i - 1, rem - 1) + 1);
    }

    return ret;
}

signed main() {
    cin >> n >> k;
    For (i, 1, n) cin >> a[i];

    memset(dp, -1, sizeof(dp));

    cout << go(n, k) << '\n';

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98244 KB Output is correct
2 Correct 43 ms 98316 KB Output is correct
3 Correct 42 ms 98284 KB Output is correct
4 Correct 43 ms 98220 KB Output is correct
5 Correct 41 ms 98248 KB Output is correct
6 Correct 43 ms 98244 KB Output is correct
7 Correct 42 ms 98304 KB Output is correct
8 Correct 43 ms 98352 KB Output is correct
9 Correct 41 ms 98252 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98244 KB Output is correct
2 Correct 43 ms 98316 KB Output is correct
3 Correct 42 ms 98284 KB Output is correct
4 Correct 43 ms 98220 KB Output is correct
5 Correct 41 ms 98248 KB Output is correct
6 Correct 43 ms 98244 KB Output is correct
7 Correct 42 ms 98304 KB Output is correct
8 Correct 43 ms 98352 KB Output is correct
9 Correct 41 ms 98252 KB Output is correct
10 Correct 42 ms 98456 KB Output is correct
11 Correct 47 ms 98552 KB Output is correct
12 Correct 86 ms 98392 KB Output is correct
13 Correct 132 ms 98440 KB Output is correct
14 Correct 149 ms 98416 KB Output is correct
15 Correct 146 ms 98404 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98244 KB Output is correct
2 Correct 43 ms 98316 KB Output is correct
3 Correct 42 ms 98284 KB Output is correct
4 Correct 43 ms 98220 KB Output is correct
5 Correct 41 ms 98248 KB Output is correct
6 Correct 43 ms 98244 KB Output is correct
7 Correct 42 ms 98304 KB Output is correct
8 Correct 43 ms 98352 KB Output is correct
9 Correct 41 ms 98252 KB Output is correct
10 Correct 42 ms 98456 KB Output is correct
11 Correct 47 ms 98552 KB Output is correct
12 Correct 86 ms 98392 KB Output is correct
13 Correct 132 ms 98440 KB Output is correct
14 Correct 149 ms 98416 KB Output is correct
15 Correct 146 ms 98404 KB Output is correct
16 Runtime error 446 ms 199220 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -