Submission #761563

#	Time	Username	Problem	Language	Result	Execution time	Memory
761563		MetalPower	Skyline (IZhO11_skyline)	C++14	100 / 100	111 ms	113620 KiB

skyline

#include <bits/stdc++.h>
using namespace std;

const int MX = 305;
const int INF = 1e9 + 7;

int N, h[MX], memo[MX][MX][MX];

int dp(int i, int p1, int p2){
	if(i == N){
		return min(p1, p2) * 2 + max(p1, p2) * 3;
		return 0;
	}
	if(memo[i][p1][p2] != -1) return memo[i][p1][p2];
	if(p2 == 0) return dp(i + 1, h[i], p1);

	int mn = INF;

	if(p1 > 0 && p2 > 0) mn = min(mn, dp(i, p1 - 1, p2 - 1) + 5);

	int tot = 0;
	int rem3 = min(h[i], min(p1, p2));
	int currh = h[i] - rem3, currp1 = p1 - rem3, currp2 = p2 - rem3;
	tot += 7 * rem3;

	int rem2 = min(currp1, currp2);
	currp1 -= rem2;
	currp2 -= rem2;
	tot += 5 * rem2;

	tot += 3 * currp2;

	mn = min(mn, dp(i + 1, currh, currp1) + tot);
	return memo[i][p1][p2] = mn;
}

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

	cin >> N;
	for(int i = 0; i < N; i++) cin >> h[i];

	if(N == 1){
		cout << h[0] * 3 << '\n';
		return 0;
	}else if(N == 2){
		cout << min(h[0], h[1]) * 5 + (max(h[0], h[1]) - min(h[0], h[1])) * 3 << '\n';
		return 0;
	}

	memset(memo, -1, sizeof memo);
	cout << dp(2, h[1], h[0]) << '\n';
}

• Subtask 1: 100 / 100