Submission #1338806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338806		Nipphitch	오렌지 출하 (JOI16_ho_t1)	C++20	100 / 100	31 ms	680 KiB

2016_ho_t1

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e4+5;
const int INF=1e14+7;

int n,m,k,a[N],dp[N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]+k;
        int mn=a[i],mx=a[i];
        for(int j=i-1;j>=1 && j>i-m;j--){
            mn=min(mn,a[j]);
            mx=max(mx,a[j]);
            dp[i]=min(dp[i],dp[j-1]+k+(i-j+1)*(mx-mn));
        }
    }
    cout << dp[n];
}

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50
• Subtask 3: 30 / 30