Submission #553793

#	Time	Username	Problem	Language	Result	Execution time	Memory
553793		Karliver	Skyline (IZhO11_skyline)	C++17	100 / 100	157 ms	99876 KiB

skyline

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

• Subtask 1: 100 / 100