oj.uz

Submission #400246

# Submission time Handle Problem Language Result Execution time Memory
400246 2021-05-07T18:01:45 Z kgh3620 Skyline (IZhO11_skyline) C++17
0 / 100
 108 ms 50116 KB 
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <unordered_set>
#include <fstream>
#include <random>

using namespace std;

int h[301];
int dp[305][205][205];

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> h[i];
	}

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

	for (int i = 0; i <= 300; i++)
	{
		for (int j = 0; j <= 200; j++)
		{
			for (int k = 0; k <= 200; k++)
			{
				dp[i][j][k] = 1e9;
			}
		}
	}

	dp[0][0][0] = 0;

	for (int i = 0; i < n + 2; i++)
	{
		for (int j = 200; j>=0; j--)
		{
			for (int k = 200;k>=0;k--)
			{
				if (dp[i][j][k] >= 1e9)
				{
					continue;
				}
				if (k - 1 >= 0)
				{
					dp[i][j][k-1] = min(dp[i][j][k-1], dp[i][j][k] + 3);
				}
				if (j - 1 >= 0 && k - 1 >= 0)
				{
					dp[i][j - 1][k - 1] = min(dp[i][j - 1][k - 1], dp[i][j][k] + 5);
				}
				if (h[i] >= j && k >= j)
				{
					dp[i + 1][k - j][h[i] - j] = min(dp[i + 1][k - j][h[i] - j], dp[i][j][k] + 7 * j);
				}
			}
		}

	}

	cout << dp[n+2][0][0] << '\n';

	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 28 ms 49732 KB Output is correct
4 Correct 31 ms 49728 KB Output is correct
5 Correct 28 ms 49732 KB Output is correct
6 Correct 28 ms 49832 KB Output is correct
7 Correct 29 ms 49764 KB Output is correct
8 Correct 30 ms 49760 KB Output is correct
9 Correct 29 ms 49756 KB Output is correct
10 Correct 30 ms 49768 KB Output is correct
11 Correct 40 ms 49732 KB Output is correct
12 Correct 31 ms 49732 KB Output is correct
13 Correct 42 ms 49740 KB Output is correct
14 Correct 49 ms 49736 KB Output is correct
15 Correct 84 ms 49812 KB Output is correct
16 Correct 81 ms 49936 KB Output is correct
17 Incorrect 108 ms 50116 KB Output isn't correct
18 Halted 0 ms 0 KB -