Submission #400228

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
400228	2021-05-07T17:39:17 Z	kgh3620	Skyline (IZhO11_skyline)	C++17	0 / 100	32 ms	49796 KB

skyline

#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];
	}

	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; i++)
	{
		for (int j = 0; j <= 200; j++)
		{
			for (int k = 0; k <= 200; k++)
			{
				if (dp[i][j][k] >= 1e9)
				{
					continue;
				}
				int a = j;
				int b = k;
				int c = h[i];
				int m = min(a, min(b, c));
				int cost = 7 * m + (a - m) * 3;
				dp[i + 1][b - m][c - m] = min(dp[i + 1][b - m][c - m], dp[i][a][b] + cost);
				m = min(a, b);
				cost = 5 * m + (a - m) * 3;
				dp[i + 1][b - m][c] = min(dp[i + 1][b - m][c], dp[i][a][b] + cost);
				dp[i + 1][0][c] = min(dp[i + 1][0][c], dp[i][a][b] + cost + (b - m) * 3);
				dp[i + 1][b - m][0] = min(dp[i + 1][b - m][0], dp[i][a][b] + cost + (c * 3));
				int M = min(b - m, c - m);
				int na = a - m;
				int nb = b - m - M;
				int nc = c - m - M;
				cost += 5 * M;
				dp[i + 1][0][nc] = min(dp[i + 1][0][nc], dp[i][a][b] + cost + 3 * nb);
				dp[i + 1][nb][0] = min(dp[i + 1][nb][0], dp[i][a][b] + cost + 3 * nc);
				cost = 3 * a;
				dp[i + 1][b][c] = min(dp[i + 1][b][c], dp[i][a][b] + cost);
			}
		}
	}

	int res = 1e9;

	for (int i = 0; i <= 200; i++)
	{
		for (int j = 0; j <= 200; j++)
		{
			if (dp[n][i][j] >= 1e9)
			{
				continue;
			}
			int m = min(i, j);
			int cost = dp[n][i][j] + 5 * m + (i - m) * 3 + (j - m) * 3;
			res = min(res, cost);
		}
	}
	cout << res << '\n';

	return 0;
}

Compilation message

skyline.cpp: In function 'int main()':
skyline.cpp:80:9: warning: unused variable 'na' [-Wunused-variable]
   80 |     int na = a - m;
      |         ^~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	49792 KB	Output is correct
2	Correct	26 ms	49796 KB	Output is correct
3	Incorrect	26 ms	49772 KB	Output isn't correct
4	Halted	0 ms	0 KB	-