Submission #960225

#	Time	Username	Problem	Language	Result	Execution time	Memory
960225		Isam	Skyline (IZhO11_skyline)	C++17	100 / 100	66 ms	49756 KiB

skyline

#include<bits/stdc++.h>
using namespace std;

constexpr int inf = 1E9;

int n, h[305], dp[305][205][205];

int f(int i, int x, int y){
	
	if(i == n + 1) return 0;
	
	if(dp[i][x][y]) return dp[i][x][y];
	
	int res = inf;
	
	if(!x) res = f(i + 1, y, h[i+2]);
	else{
		
		res = min(res, f(i, x - 1, y) + 3);
		
		if(y){
			
			res = min(res, f(i, x - 1, y - 1) + 5);
			
			if(x <= min(y, h[i + 2])) res = min(res, f(i + 1, y - x, h[i + 2] - x) + 7 * x);
			
		}
		
	}
	
	return dp[i][x][y] = res;
	
}

/*
dp[i][x][y] -> dp[i][x+1][y] + 3,   dp[i][x+1][y+1] + 5, dp[i-1][]

dp[i][x-1][y] dp[i][x][y] + 3

dp[i][x-1][y-1]  dp[i][x][y] + 5

dp[i+1][y - x][h[i + 2] - x]  dp[i][x][y] + 7 * x; 	

*/



signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	register int j(1);
	loop:
		cin >> h[j++];
	if(j <= n) goto loop;
	
	for(register int i = 0; i <= n; ++i){
		for(register int j = 0; j < 205; ++j){
			for(register int m = 0; m < 205; ++m){
				dp[i][j][m] = inf;
			}
		}
	}
	
	dp[1][h[1]][h[2]] = 0;
	
	for(register int i = 1; i <= n; ++i){
		for(register int x = h[i]; x >= 0; --x){
			for(register int y = h[i+1]; y >= 0; --y){
				
				if(x) dp[i][x - 1][y] = min(dp[i][x - 1][y], dp[i][x][y] + 3);
				
				if(x && y) dp[i][x - 1][y - 1] = min(dp[i][x -1 ][y - 1], dp[i][x][y] + 5);
				
				if(x <= min(y, h[i + 2])) dp[i + 1][y - x][h[i + 2] - x] = min(dp[i + 1][y - x][h[i + 2] - x], dp[i][x][y] + 7 * x);
				
			}
		}
	}
	
	cout << dp[n][0][0] << '\n';
	
	return 0;
}

Compilation message (stderr)

skyline.cpp: In function 'int main()':
skyline.cpp:51:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |  register int j(1);
      |               ^
skyline.cpp:56:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   56 |  for(register int i = 0; i <= n; ++i){
      |                   ^
skyline.cpp:57:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   57 |   for(register int j = 0; j < 205; ++j){
      |                    ^
skyline.cpp:58:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   58 |    for(register int m = 0; m < 205; ++m){
      |                     ^
skyline.cpp:66:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   66 |  for(register int i = 1; i <= n; ++i){
      |                   ^
skyline.cpp:67:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   67 |   for(register int x = h[i]; x >= 0; --x){
      |                    ^
skyline.cpp:68:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   68 |    for(register int y = h[i+1]; y >= 0; --y){
      |                     ^

• Subtask 1: 100 / 100