oj.uz

Submission #831984

# Submission time Handle Problem Language Result Execution time Memory
831984 2023-08-20T19:08:14 Z konber Stove (JOI18_stove) C++14
50 / 100
 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", &times[i]);

    memset(memo, -1, sizeof memo);
    cout << dp(0, K) << endl;
}

Compilation message

stove.cpp: In function 'int main()':
stove.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d%d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~
stove.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%lld", &times[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 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

Subtask #2
30.0 / 30.0

# 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

Subtask #3
0 / 50.0

# 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 -