Submission #553793

# Submission time Handle Problem Language Result Execution time Memory
553793 2022-04-27T05:51:48 Z Karliver Skyline (IZhO11_skyline) C++17
100 / 100
157 ms 99876 KB
#include <bits/stdc++.h>

using namespace std;
const int mxn = 2e5 + 10;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)



const long long MOD = 998244353;
int dp[301][202][202];
int vis[301][202][202];
int h[302];
void ckmi(int &a, int b) {
	a = (b < a ? b : a);
}
int n;
int dfs(int i, int  g1, int g2) {
	if(i == n)
		return 0;
	if(vis[i][g1][g2]) return dp[i][g1][g2];
	vis[i][g1][g2] = 1;
	int &res = dp[i][g1][g2];
	res = MOD;
	if(g1 > 0) {
		ckmi(res, dfs(i, g1 - 1, g2) + 3);
		if(g2 > 0) {
			ckmi(res, dfs(i, g1 - 1, g2 - 1) + 5);
			if(g1 <= min(g2, h[i + 2]))ckmi(res, dfs(i + 1, g2 - g1, h[i + 2] - g1) + 7 * g1);
		}
	}
	else ckmi(res, dfs(i + 1, g2, h[i + 2]));
	return res;
}
void test_case() {
	
	
	
	cin >> n;
	
	for(int i = 0;i < n;++i) {
		cin >> h[i];
	}
	cout << dfs(0, h[0], h[1]) << '\n';
				
}
					
		

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tt;
	tt = 1;
	//cin >> tt;
	
	for(int p = 1;p <= tt;++p) {
		//cout << "Case #" << p << ": ";
		test_case();
	}
	
		
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 2004 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 840 KB Output is correct
8 Correct 1 ms 1104 KB Output is correct
9 Correct 2 ms 2120 KB Output is correct
10 Correct 4 ms 4564 KB Output is correct
11 Correct 23 ms 23872 KB Output is correct
12 Correct 6 ms 5964 KB Output is correct
13 Correct 30 ms 26692 KB Output is correct
14 Correct 44 ms 37176 KB Output is correct
15 Correct 123 ms 79360 KB Output is correct
16 Correct 112 ms 73564 KB Output is correct
17 Correct 157 ms 99824 KB Output is correct
18 Correct 149 ms 98452 KB Output is correct
19 Correct 140 ms 92908 KB Output is correct
20 Correct 151 ms 99876 KB Output is correct