#include<bits/stdc++.h>
using namespace std;
int dp[305][205][205];
int n;
int a[305];
int op3(int i, int &n1, int &n2) {
int x = n1, y = n2, z = a[i+2];
int ret = 0;
int take = min({x, y, z});
ret = take * 7;
x -= take;
y -= take;
z -= take;
if(x) {
if(y) {
take = min(x, y);
ret += take * 5;
x -= take;
y -= take;
if(x) {
ret += x * 3;
}
} else {
ret += x * 3;
}
}
n1 = y, n2 = z;
return ret;
}
int solve(int i, int n1, int n2) {
if(i>n) return 0;
int &ret = dp[i][n1][n2];
if(ret!=-1) return ret;
ret = solve(i+1, n2, a[i+2]) + n1 * 3;
ret = solve(i+1, max(0, n2-n1), a[i+2]) + min(n1, n2) * 5 + max(n1-n2, 0) * 3;
int c = op3(i, n1, n2);
ret = min(ret, c+solve(i+1, n1, n2));
return ret;
}
void PlayGround() {
cin>>n;
for(int i=1; i<=n; ++i) {
cin>>a[i];
}
memset(dp, -1, sizeof dp);
cout<<solve(1, a[1], a[2])<<'\n';
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
50388 KB |
Output is correct |
| 2 |
Correct |
20 ms |
50448 KB |
Output is correct |
| 3 |
Correct |
23 ms |
50468 KB |
Output is correct |
| 4 |
Correct |
20 ms |
50372 KB |
Output is correct |
| 5 |
Correct |
20 ms |
50428 KB |
Output is correct |
| 6 |
Incorrect |
20 ms |
50448 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
