Submission #1279205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279205		SmuggingSpun	Skyline (IZhO11_skyline)	C++20	100 / 100	115 ms	57128 KiB

skyline

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int lim = 305;
const int LIM = 205;
const int INF = 1e9;
int n, a[lim], f[lim][LIM][LIM];
int dp(int p, int a1, int a2){
	if(p < 1 || a1 < 0 || a2 < 0){
		return INF;
	}
	int& ans = f[p][a1][a2];
	if(ans != -1){
		return ans;
	}
	if(p == 1){
		vector<int>b = {a[p], a1, a2};
		int x = min({b[0], b[1], b[2]});
		for(int i = 0; i < 3; i++){
			b[i] -= x;
		}
		if(b[0] > 0 && b[1] > 0){
			return ans = x * 7 + (min(b[0], b[1]) << 1) + max(b[0], b[1]) * 3;
		}
		if(b[1] > 0 && b[2] > 0){
			return ans = x * 7 + (min(b[1], b[2]) << 1) + max(b[1], b[2]) * 3;
		}
		return ans = x * 7 + (b[0] + b[1] + b[2]) * 3;
	}
	if(a2 == 0){
		return ans = dp(p - 1, a[p], a1);
	}
	return ans = min({dp(p, a1, a2 - 1) + 3, dp(p, a1 - 1, a2 - 1) + 5, dp(p - 1, a[p] - a2, a1 - a2) + 7 * a2});
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	if(n == 1){
		return cout << a[1] * 3, 0;
	}
	if(n == 2){
		return cout << (min(a[1], a[2]) << 1) + max(a[1], a[2]) * 3, 0;
	}
	memset(f, -1, sizeof(f));
	cout << dp(n - 2, a[n - 1], a[n]);
}

Compilation message (stderr)

skyline.cpp: In function 'int main()':
skyline.cpp:38:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100