oj.uz

Submission #4882

# Submission time Handle Problem Language Result Execution time Memory
4882 2014-01-06T11:55:59 Z tncks0121 Skyline (IZhO11_skyline) C++
95 / 100
 252 ms 57524 KB 
#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) {
		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(x < 1 || h1 < 0 || h2 < 0) return 10000000;
	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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 51156 KB Output is correct
2 Correct 0 ms 51156 KB Output is correct
3 Correct 4 ms 51156 KB Output is correct
4 Correct 0 ms 51156 KB Output is correct
5 Correct 12 ms 51156 KB Output is correct
6 Correct 4 ms 51156 KB Output is correct
7 Correct 4 ms 51156 KB Output is correct
8 Incorrect 8 ms 51156 KB Output isn't correct
9 Correct 0 ms 51156 KB Output is correct
10 Correct 16 ms 51252 KB Output is correct
11 Correct 36 ms 52484 KB Output is correct
12 Correct 20 ms 51356 KB Output is correct
13 Correct 28 ms 52656 KB Output is correct
14 Correct 60 ms 53328 KB Output is correct
15 Correct 168 ms 56072 KB Output is correct
16 Correct 176 ms 55696 KB Output is correct
17 Correct 252 ms 57524 KB Output is correct
18 Correct 236 ms 57336 KB Output is correct
19 Correct 212 ms 56972 KB Output is correct
20 Correct 244 ms 57492 KB Output is correct