# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
831984 | 2023-08-20T19:08:14 Z | konber | Stove (JOI18_stove) | C++14 | 155 ms | 198348 KB |
#include <iostream> #include <vector> #include <cstring> using namespace std; typedef long long ll; vector<ll> times; ll memo[5005][5005]; int N; ll dp(int i, int remK){ if(remK < 0) return 1e15; if(i==N) return 0; if(memo[i][remK] != -1) return memo[i][remK]; ll ch1=1e15; if(i){ ch1 = dp(i+1, remK) + times[i]+1 - times[i-1]-1; } ll ch2 = dp(i+1, remK-1) + 1; return memo[i][remK] = min(ch1, ch2); } int main() { int K; scanf("%d%d", &N, &K); times.resize(N); for(int i=0; i < N; i++) scanf("%lld", ×[i]); memset(memo, -1, sizeof memo); cout << dp(0, K) << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 77 ms | 196268 KB | Output is correct |
2 | Correct | 59 ms | 196300 KB | Output is correct |
3 | Correct | 58 ms | 196344 KB | Output is correct |
4 | Correct | 60 ms | 196316 KB | Output is correct |
5 | Correct | 59 ms | 196304 KB | Output is correct |
6 | Correct | 59 ms | 196300 KB | Output is correct |
7 | Correct | 58 ms | 196336 KB | Output is correct |
8 | Correct | 65 ms | 196372 KB | Output is correct |
9 | Correct | 59 ms | 196296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 77 ms | 196268 KB | Output is correct |
2 | Correct | 59 ms | 196300 KB | Output is correct |
3 | Correct | 58 ms | 196344 KB | Output is correct |
4 | Correct | 60 ms | 196316 KB | Output is correct |
5 | Correct | 59 ms | 196304 KB | Output is correct |
6 | Correct | 59 ms | 196300 KB | Output is correct |
7 | Correct | 58 ms | 196336 KB | Output is correct |
8 | Correct | 65 ms | 196372 KB | Output is correct |
9 | Correct | 59 ms | 196296 KB | Output is correct |
10 | Correct | 59 ms | 196512 KB | Output is correct |
11 | Correct | 64 ms | 196620 KB | Output is correct |
12 | Correct | 94 ms | 196540 KB | Output is correct |
13 | Correct | 121 ms | 196612 KB | Output is correct |
14 | Correct | 139 ms | 196604 KB | Output is correct |
15 | Correct | 155 ms | 196600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 77 ms | 196268 KB | Output is correct |
2 | Correct | 59 ms | 196300 KB | Output is correct |
3 | Correct | 58 ms | 196344 KB | Output is correct |
4 | Correct | 60 ms | 196316 KB | Output is correct |
5 | Correct | 59 ms | 196304 KB | Output is correct |
6 | Correct | 59 ms | 196300 KB | Output is correct |
7 | Correct | 58 ms | 196336 KB | Output is correct |
8 | Correct | 65 ms | 196372 KB | Output is correct |
9 | Correct | 59 ms | 196296 KB | Output is correct |
10 | Correct | 59 ms | 196512 KB | Output is correct |
11 | Correct | 64 ms | 196620 KB | Output is correct |
12 | Correct | 94 ms | 196540 KB | Output is correct |
13 | Correct | 121 ms | 196612 KB | Output is correct |
14 | Correct | 139 ms | 196604 KB | Output is correct |
15 | Correct | 155 ms | 196600 KB | Output is correct |
16 | Incorrect | 68 ms | 198348 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |