oj.uz

Submission #487241

# Submission time Handle Problem Language Result Execution time Memory
487241 2021-11-14T22:05:43 Z ala2 Stove (JOI18_stove) C++14
50 / 100
 166 ms 201272 KB 
#include <bits/stdc++.h>

using namespace std;
int dp[5010][5010];
int t[1001000];
int f(int i,int k)
{
    //cout<<"        "<<i<<"  "<<k<<endl;
    if(dp[i][k]!=-1)
        return dp[i][k];
    if(k<=0)
        return 1000000000;
    if(i==0)
        return 1;
    return dp[i][k]=min(f(i-1,k-1)+1,f(i-1,k)+t[i]+1-t[i-1]);

}
int main()
{
    int n,k;
    cin>>n>>k;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++)
        cin>>t[i];
    cout<<f(n-1,k)-n+k;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98500 KB Output is correct
2 Correct 49 ms 98528 KB Output is correct
3 Correct 41 ms 98508 KB Output is correct
4 Correct 41 ms 98428 KB Output is correct
5 Correct 42 ms 98444 KB Output is correct
6 Correct 49 ms 98432 KB Output is correct
7 Correct 42 ms 98536 KB Output is correct
8 Correct 44 ms 98400 KB Output is correct
9 Correct 41 ms 98460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98500 KB Output is correct
2 Correct 49 ms 98528 KB Output is correct
3 Correct 41 ms 98508 KB Output is correct
4 Correct 41 ms 98428 KB Output is correct
5 Correct 42 ms 98444 KB Output is correct
6 Correct 49 ms 98432 KB Output is correct
7 Correct 42 ms 98536 KB Output is correct
8 Correct 44 ms 98400 KB Output is correct
9 Correct 41 ms 98460 KB Output is correct
10 Correct 42 ms 98660 KB Output is correct
11 Correct 46 ms 98612 KB Output is correct
12 Correct 75 ms 98600 KB Output is correct
13 Correct 105 ms 98600 KB Output is correct
14 Correct 124 ms 98628 KB Output is correct
15 Correct 134 ms 98624 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98500 KB Output is correct
2 Correct 49 ms 98528 KB Output is correct
3 Correct 41 ms 98508 KB Output is correct
4 Correct 41 ms 98428 KB Output is correct
5 Correct 42 ms 98444 KB Output is correct
6 Correct 49 ms 98432 KB Output is correct
7 Correct 42 ms 98536 KB Output is correct
8 Correct 44 ms 98400 KB Output is correct
9 Correct 41 ms 98460 KB Output is correct
10 Correct 42 ms 98660 KB Output is correct
11 Correct 46 ms 98612 KB Output is correct
12 Correct 75 ms 98600 KB Output is correct
13 Correct 105 ms 98600 KB Output is correct
14 Correct 124 ms 98628 KB Output is correct
15 Correct 134 ms 98624 KB Output is correct
16 Runtime error 166 ms 201272 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -