Submission #895062

#	Time	Username	Problem	Language	Result	Execution time	Memory
895062		MongHwa	오렌지 출하 (JOI16_ho_t1)	C++17	100 / 100	110 ms	2508 KiB

2016_ho_t1

#include <iostream>
#include <cstring>
using namespace std;

#define ll long long
#define INF 1e16

int n, m, k;
ll arr[20001], dp[20001];

ll go(int pos)
{
	if(pos == n)
		return 0;

	ll& ret = dp[pos];
	if(ret != -1)
		return ret;

	ret = INF;
	ll mx = arr[pos], mn = arr[pos];
	for(int i = pos; i < min(n, pos+m); i++)
	{
		mx = max(mx, arr[i]);
		mn = min(mn, arr[i]);
		ret = min(ret, (i-pos+1)*(mx-mn)+k + go(i+1));
	}

	return ret;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dp, -1, sizeof(dp));

	cin >> n >> m >> k;
	for(int i = 0; i < n; i++)
		cin >> arr[i];

	cout << go(0) << '\n';
}

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