#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 3e2 +23, inf = LLONG_MAX, LG = 20;
int dp[sze][sze];
void fast(){
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
if(i){
dp[i][0] = dp[i-1][arr[i-1]];
}
if(i){
for(int curr=1;curr<=arr[i];curr++){
if(i<2){
int sil = (min(arr[i-1],curr));
dp[i][curr] = min(sil*5 + ( (curr - sil) + (arr[i-1] - sil) )*3, dp[i-1][arr[i-1]] + curr*3);
}
else{
int sil3 = min({ arr[i-2],arr[i-1],curr });
int sil2 = min({ arr[i-1] - sil3, curr - sil3 });
dp[i][curr] = (sil3*7) + sil2*5 + dp[i-2][arr[i-2] - sil3] + (arr[i-1] - sil3 - sil2)*3 + (curr - sil2-sil3)*3;
}
// cout<<i<<" "<<curr<<" => "<<dp[i][curr]<<endl;
}
}
else{
for(int curr=1;curr<=arr[i];curr++){
dp[0][curr]= (curr*3 );
}
}
}
putr(dp[n-1][ arr[n-1] ]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
fast();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
