oj.uz

Submission #638915

# Submission time Handle Problem Language Result Execution time Memory
638915 2022-09-07T23:10:25 Z rc_catunta Stove (JOI18_stove) C++14
50 / 100
 112 ms 99800 KB 
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int INF = 1000000010;
int memo[5001][5001];
vi guests;
int N,K,x;

int dp(int g,int m){
    // Casos Base
    if(m>K) return INF;
    if(g==N-1) return 1;
    // Memoizacion
    if(memo[g][m]!=-1) return memo[g][m];
    // Busqueda
    int res = min(1+dp(g+1,m+1),guests[g+1]-guests[g]+dp(g+1,m));
    return memo[g][m]=res;
}

int main(){
    ios_base::sync_with_stdio(false);
    memset(memo,-1,sizeof(memo));
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>x;
        guests.push_back(x);
    }
    cout<<dp(0,1)<<"\n";
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98104 KB Output is correct
2 Correct 38 ms 98100 KB Output is correct
3 Correct 40 ms 98188 KB Output is correct
4 Correct 38 ms 98144 KB Output is correct
5 Correct 37 ms 98084 KB Output is correct
6 Correct 38 ms 98108 KB Output is correct
7 Correct 39 ms 98120 KB Output is correct
8 Correct 40 ms 98168 KB Output is correct
9 Correct 47 ms 98168 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98104 KB Output is correct
2 Correct 38 ms 98100 KB Output is correct
3 Correct 40 ms 98188 KB Output is correct
4 Correct 38 ms 98144 KB Output is correct
5 Correct 37 ms 98084 KB Output is correct
6 Correct 38 ms 98108 KB Output is correct
7 Correct 39 ms 98120 KB Output is correct
8 Correct 40 ms 98168 KB Output is correct
9 Correct 47 ms 98168 KB Output is correct
10 Correct 38 ms 98284 KB Output is correct
11 Correct 41 ms 98312 KB Output is correct
12 Correct 76 ms 98380 KB Output is correct
13 Correct 106 ms 98396 KB Output is correct
14 Correct 100 ms 98384 KB Output is correct
15 Correct 112 ms 98380 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98104 KB Output is correct
2 Correct 38 ms 98100 KB Output is correct
3 Correct 40 ms 98188 KB Output is correct
4 Correct 38 ms 98144 KB Output is correct
5 Correct 37 ms 98084 KB Output is correct
6 Correct 38 ms 98108 KB Output is correct
7 Correct 39 ms 98120 KB Output is correct
8 Correct 40 ms 98168 KB Output is correct
9 Correct 47 ms 98168 KB Output is correct
10 Correct 38 ms 98284 KB Output is correct
11 Correct 41 ms 98312 KB Output is correct
12 Correct 76 ms 98380 KB Output is correct
13 Correct 106 ms 98396 KB Output is correct
14 Correct 100 ms 98384 KB Output is correct
15 Correct 112 ms 98380 KB Output is correct
16 Incorrect 49 ms 99800 KB Output isn't correct
17 Halted 0 ms 0 KB -