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