Submission #732831

#	Time	Username	Problem	Language	Result	Execution time	Memory
732831		flappybird	오렌지 출하 (JOI16_ho_t1)	C++17	100 / 100	130 ms	948 KiB

2016_ho_t1

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
ll arr[MAX];
ll dp[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M;
	ll K;
	cin >> N >> M >> K;
	int i, j;
	for (i = 1; i <= N; i++) cin >> arr[i];
	for (i = 1; i <= N; i++) {
		dp[i] = dp[i - 1] + K;
		ll mn, mx;
		mn = mx = arr[i];
		for (j = i; j > i - M; j--) {
			if (!j) break;
			mn = min(mn, arr[j]);
			mx = max(mx, arr[j]);
			dp[i] = min(dp[i], (mx - mn) * (i - j + 1) + K + dp[j - 1]);
		}
	}
	cout << dp[N] << ln;
}

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