제출 #1322496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1322496		aaaaaaaa	스카이라인 (IZhO11_skyline)	C++20	100 / 100	127 ms	222512 KiB

skyline

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


#define int long long

const int inf = 5e18;

const int mxN = 305;

int dp[mxN][mxN][mxN], a[mxN];


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	for(int i = 0; i < mxN; ++i){
		for(int j = 0; j < mxN; ++j){
			for(int k = 0; k < mxN; ++k){
				dp[i][j][k] = inf;
			}
		}
	}
	if(n == 1){
		cout << a[1] * 3 << "\n";
	}else if(n == 2){
		cout << min(min(a[1], a[2]) * 5 + abs(a[1] - a[2]) * 3, a[1] * 3 + a[2] * 3) << "\n";
	}else{
		for(int i = 0; i <= a[1]; ++i){
			dp[1][0][a[1] - i] = dp[2][a[1] - i][a[2]] = i * 3;
		}
		for(int i = 2; i <= n; ++i){
			for(int prev = a[i - 1]; prev >= 0; --prev){
				for(int cur = a[i]; cur >= 0; --cur){
					dp[i][prev][cur] = min(dp[i][prev][cur], dp[i][prev][cur + 1] + 3);
				}
			}
			for(int prev = a[i - 1]; prev >= 0; --prev){
				for(int cur = a[i]; cur >= 0; --cur){
					dp[i][prev][cur] = min(dp[i][prev][cur], dp[i][prev + 1][cur + 1] + 5);
				}
			}
			if(i == n) break;
			for(int j = min({a[i - 1], a[i], a[i + 1]}); j >= 0; --j){
				for(int cur = a[i]; cur >= j; --cur){
					dp[i + 1][cur - j][a[i + 1] - j] = min(dp[i + 1][cur - j][a[i + 1] - j], dp[i][j][cur] + 7ll * j);
				}
			}
		}
		cout << dp[n][0][0] << "\n";
	}
	return 0;
}

• Subtask 1: 100 / 100