oj.uz

Submission #735372

# Submission time Handle Problem Language Result Execution time Memory
735372 2023-05-04T04:33:23 Z That_Salamander Stove (JOI18_stove) C++17
50 / 100
 187 ms 199176 KB 
#include <bits/stdc++.h>
#define int long long

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int n, k;
int t[100005];
int ds[100005];
int dp[5005][5005];

int solve(int idx, int kLeft) {
    if (kLeft < 0) return 1000000000;
    if (idx >= n - 1) return 0;
    if (dp[idx][kLeft] != -1) return dp[idx][kLeft];

    return dp[idx][kLeft] = min(ds[idx] + solve(idx + 1, kLeft), solve(idx + 1, kLeft - 1));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> k;

    FOR (i, n) {
        cin >> t[i];
    }

    FOR (i, n - 1) {
        ds[i] = t[i+1] - t[i] - 1;
    }

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

    cout << n + solve(0, k - 1) << endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196356 KB Output is correct
2 Correct 76 ms 196400 KB Output is correct
3 Correct 72 ms 196356 KB Output is correct
4 Correct 71 ms 196392 KB Output is correct
5 Correct 82 ms 196360 KB Output is correct
6 Correct 86 ms 196300 KB Output is correct
7 Correct 76 ms 196312 KB Output is correct
8 Correct 72 ms 196348 KB Output is correct
9 Correct 76 ms 196368 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196356 KB Output is correct
2 Correct 76 ms 196400 KB Output is correct
3 Correct 72 ms 196356 KB Output is correct
4 Correct 71 ms 196392 KB Output is correct
5 Correct 82 ms 196360 KB Output is correct
6 Correct 86 ms 196300 KB Output is correct
7 Correct 76 ms 196312 KB Output is correct
8 Correct 72 ms 196348 KB Output is correct
9 Correct 76 ms 196368 KB Output is correct
10 Correct 81 ms 196552 KB Output is correct
11 Correct 101 ms 196580 KB Output is correct
12 Correct 136 ms 196652 KB Output is correct
13 Correct 153 ms 196668 KB Output is correct
14 Correct 187 ms 196664 KB Output is correct
15 Correct 160 ms 196668 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196356 KB Output is correct
2 Correct 76 ms 196400 KB Output is correct
3 Correct 72 ms 196356 KB Output is correct
4 Correct 71 ms 196392 KB Output is correct
5 Correct 82 ms 196360 KB Output is correct
6 Correct 86 ms 196300 KB Output is correct
7 Correct 76 ms 196312 KB Output is correct
8 Correct 72 ms 196348 KB Output is correct
9 Correct 76 ms 196368 KB Output is correct
10 Correct 81 ms 196552 KB Output is correct
11 Correct 101 ms 196580 KB Output is correct
12 Correct 136 ms 196652 KB Output is correct
13 Correct 153 ms 196668 KB Output is correct
14 Correct 187 ms 196664 KB Output is correct
15 Correct 160 ms 196668 KB Output is correct
16 Incorrect 84 ms 199176 KB Output isn't correct
17 Halted 0 ms 0 KB -