oj.uz

Submission #960225

# Submission time Handle Problem Language Result Execution time Memory
960225 2024-04-10T00:05:01 Z Isam Skyline (IZhO11_skyline) C++17
100 / 100
 66 ms 49756 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 12 ms 25180 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 14 ms 29276 KB Output is correct
14 Correct 20 ms 33368 KB Output is correct
15 Correct 50 ms 45760 KB Output is correct
16 Correct 45 ms 41564 KB Output is correct
17 Correct 66 ms 49756 KB Output is correct
18 Correct 62 ms 49500 KB Output is correct
19 Correct 62 ms 47704 KB Output is correct
20 Correct 64 ms 49752 KB Output is correct