oj.uz

Submission #914412

# Submission time Handle Problem Language Result Execution time Memory
914412 2024-01-22T04:59:19 Z Aiperiii Stove (JOI18_stove) C++14
50 / 100
 52 ms 236372 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=5e3+5;
int dp[N][N],x[N][N];
signed main(){
    int n,k;
    cin>>n>>k;
    vector <int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<k;i++){
        for(int j=0;j<n;j++){
            x[i][j]=1e9;
        }
    }
    for(int i=0;i<n;i++){
        dp[0][i]=a[i]+1-a[0];
        if(i-1>=0 && i+1<n)x[0][i]=min(x[0][i-1],dp[0][i]-a[i+1]);
        else if(i==0 && i+1<n)x[0][i]=dp[0][i]-a[i+1];
    }
    
    for(int i=1;i<k;i++){
        for(int j=0;j<n;j++){
            if(j-1>=0)dp[i][j]=a[j]+1+x[i-1][j-1];
            if(j-1>=0 && j+1<n){
                x[i][j]=min(x[i][j-1],dp[i][j]-a[j+1]);
            }
        }
    }
    cout<<dp[k-1][n-1];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 4696 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 19 ms 80604 KB Output is correct
13 Correct 39 ms 160596 KB Output is correct
14 Correct 49 ms 230224 KB Output is correct
15 Correct 52 ms 236372 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 4696 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 19 ms 80604 KB Output is correct
13 Correct 39 ms 160596 KB Output is correct
14 Correct 49 ms 230224 KB Output is correct
15 Correct 52 ms 236372 KB Output is correct
16 Incorrect 34 ms 8148 KB Output isn't correct
17 Halted 0 ms 0 KB -