Submission #4883

#	Time	Username	Problem	Language	Result	Execution time	Memory
4883		tncks0121	Skyline (IZhO11_skyline)	C++98	100 / 100	264 ms	57528 KiB

skyline

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

int N, A[305];
int Table[305][205][205];

int solve (int x, int h1, int h2) {
	if(x < 1 || h1 < 0 || h2 < 0) return 10000000;

	if(x == 1) {
		int h[] = {A[1], h1, h2};
		int m = *min_element(h, h+3);
		for(int i = 0; i < 3; i++) h[i] -= m;
		for(int i = 0; i < 2; i++) if(h[i] > 0 && h[i+1] > 0) return 7*m + 5*min(h[i], h[i+1]) + 3*abs(h[i]-h[i+1]);
		return 7*m + 3*(h[0]+h[1]+h[2]);
	}

	if(h2 == 0) return solve(x-1, A[x], h1);

	int &ret = Table[x][h1][h2];
	if(ret >= 0) return ret;

	int candidates[] = {
		solve(x, h1, h2-1) + 3,
		solve(x, h1-1, h2-1) + 5,
		solve(x-1, A[x] - h2, h1 - h2) + h2 * 7,
	};

	ret = *min_element(candidates, candidates+3);
	return ret;
}

int main() {
	int i, j, k;

	scanf("%d", &N);
	for(i = 1; i <= N; i++) scanf("%d", A+i);
	
	if(N == 1) {
		printf("%d\n", A[1] * 3);
		return 0;
	}

	if(N == 2) {
		int t = min(A[1], A[2]);
		printf("%d\n", 5*t + 3*(A[1]-t+A[2]-t));
		return 0;
	}

	memset(Table, -1, sizeof Table);

	printf("%d\n", solve(N-2, A[N-1], A[N]));



	return 0;
}

• Subtask 1: 100 / 100