oj.uz

Submission #914411

# Submission time Handle Problem Language Result Execution time Memory
914411 2024-01-22T04:49:22 Z Aiperiii Stove (JOI18_stove) C++14
0 / 100
 1 ms 4444 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<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]);
            else if(j==0 && j+1<n)x[i][j]=dp[i][j]-a[j+1];
        }
    }
    cout<<dp[k-1][n-1];
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 Incorrect 1 ms 4440 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 Incorrect 1 ms 4440 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 Incorrect 1 ms 4440 KB Output isn't correct
6 Halted 0 ms 0 KB -