oj.uz

Submission #470835

# Submission time Handle Problem Language Result Execution time Memory
470835 2021-09-05T22:53:59 Z jalsol Stove (JOI18_stove) C++17
50 / 100
 457 ms 199476 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];

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

    fill_n(*dp, maxn * maxn, inf);

    Rep (j, k + 1) dp[0][j] = 0;

    For (j, 1, k) {
        int mn = inf;
        For (i, 1, n) {
            chmin(mn, dp[i - 1][j - 1] - a[i]);
            dp[i][j] = a[i] + mn + 1;
        }
    }

    cout << dp[n][k] << '\n';

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98324 KB Output is correct
2 Correct 52 ms 98272 KB Output is correct
3 Correct 52 ms 98316 KB Output is correct
4 Correct 52 ms 98264 KB Output is correct
5 Correct 52 ms 98216 KB Output is correct
6 Correct 50 ms 98240 KB Output is correct
7 Correct 52 ms 98292 KB Output is correct
8 Correct 51 ms 98268 KB Output is correct
9 Correct 52 ms 98228 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98324 KB Output is correct
2 Correct 52 ms 98272 KB Output is correct
3 Correct 52 ms 98316 KB Output is correct
4 Correct 52 ms 98264 KB Output is correct
5 Correct 52 ms 98216 KB Output is correct
6 Correct 50 ms 98240 KB Output is correct
7 Correct 52 ms 98292 KB Output is correct
8 Correct 51 ms 98268 KB Output is correct
9 Correct 52 ms 98228 KB Output is correct
10 Correct 53 ms 98264 KB Output is correct
11 Correct 56 ms 98328 KB Output is correct
12 Correct 80 ms 98372 KB Output is correct
13 Correct 106 ms 98472 KB Output is correct
14 Correct 131 ms 98384 KB Output is correct
15 Correct 133 ms 98344 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98324 KB Output is correct
2 Correct 52 ms 98272 KB Output is correct
3 Correct 52 ms 98316 KB Output is correct
4 Correct 52 ms 98264 KB Output is correct
5 Correct 52 ms 98216 KB Output is correct
6 Correct 50 ms 98240 KB Output is correct
7 Correct 52 ms 98292 KB Output is correct
8 Correct 51 ms 98268 KB Output is correct
9 Correct 52 ms 98228 KB Output is correct
10 Correct 53 ms 98264 KB Output is correct
11 Correct 56 ms 98328 KB Output is correct
12 Correct 80 ms 98372 KB Output is correct
13 Correct 106 ms 98472 KB Output is correct
14 Correct 131 ms 98384 KB Output is correct
15 Correct 133 ms 98344 KB Output is correct
16 Runtime error 457 ms 199476 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -