oj.uz

Submission #400243

# Submission time Handle Problem Language Result Execution time Memory
400243 2021-05-07T17:57:15 Z kgh3620 Skyline (IZhO11_skyline) C++17
0 / 100
 30 ms 49824 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[2][h[0]][h[1]] = 0;
 
	for (int i = 0; i < n + 2; 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;
				dp[i + 1][b - m][c - m] = min(dp[i + 1][b - m][c - m], dp[i][a][b] + cost + 3*(a-m));
				int M = min(a - m, b - m);
				int na = a - m - M;
				int nb = b - m - M;
				cost += (5 * M);
				dp[i + 1][nb][c - m] = min(dp[i + 1][nb][c - m], dp[i][a][b] + cost + 3 * na);
				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);
				cost = 3 * a;
				dp[i + 1][b][c] = min(dp[i + 1][b][c], dp[i][a][b] + cost);
			}
		}
	}
 
	int res = 1e9;
 
	cout << dp[n + 2][0][0] << '\n';
 
	return 0;
}

Compilation message

skyline.cpp: In function 'int main()':
skyline.cpp:100:6: warning: unused variable 'res' [-Wunused-variable]
  100 |  int res = 1e9;
      |      ^~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 27 ms 49824 KB Output is correct
4 Correct 30 ms 49812 KB Output is correct
5 Correct 27 ms 49780 KB Output is correct
6 Incorrect 27 ms 49716 KB Output isn't correct
7 Halted 0 ms 0 KB -