Submission #960218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960218	2024-04-09T23:22:34 Z	Isam	Skyline (IZhO11_skyline)	C++17	100 / 100	110 ms	55376 KB

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



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;
	
	cout << f(1, h[1], h[2]) << '\n';
	
	return 0;
}

Compilation message

skyline.cpp: In function 'int main()':
skyline.cpp:40:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   40 |  register int j(1);
      |               ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	1372 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct
7	Correct	0 ms	720 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	2 ms	1372 KB	Output is correct
10	Correct	3 ms	2652 KB	Output is correct
11	Correct	13 ms	13016 KB	Output is correct
12	Correct	4 ms	3420 KB	Output is correct
13	Correct	15 ms	14684 KB	Output is correct
14	Correct	23 ms	20308 KB	Output is correct
15	Correct	94 ms	43348 KB	Output is correct
16	Correct	69 ms	40124 KB	Output is correct
17	Correct	102 ms	55376 KB	Output is correct
18	Correct	110 ms	53844 KB	Output is correct
19	Correct	90 ms	50768 KB	Output is correct
20	Correct	100 ms	55128 KB	Output is correct