oj.uz

Submission #339534

# Submission time Handle Problem Language Result Execution time Memory
339534 2020-12-25T15:28:27 Z tengiz05 Skyline (IZhO11_skyline) C++17
100 / 100
 215 ms 117100 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
template<class T> bool chmin(T& a, const T& b){return a>b?a=b,true:false;}
template<class T> bool chmax(T& a, const T& b){return a<b?a=b,true:false;}
const int N = 305;
int n;
int a[N];
int dp[N][N][N];
int get_ans(int x, int y){
  int mn = min(x, y);
  int mx = max(x, y);
  return mn*5+(mx-mn)*3;  
}
int calc(int i, int x, int y){
  if(~dp[i][x][y])return dp[i][x][y];
  int &ret = dp[i][x][y];
  ret = 100000000;
  if(i == n+1)return ret = get_ans(x, y);
  if(x>0)chmin(ret, calc(i, x-1, y)+3);
  if(x>0 && y>0)chmin(ret, calc(i,x-1,y-1)+5);
  if(x == 0)chmin(ret, calc(i+1, y, a[i]));
  if(x == min(x, min(y, a[i])))chmin(ret, calc(i+1, y-x, a[i]-x) + x*7);
  return ret;
}

void Solve(){
  cin >> n;
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }
  if(n == 1){
    cout << a[1]*3 << '\n';
  }else if(n == 2){
    cout << get_ans(a[1], a[2]) << '\n';
  }else {
    memset(dp, -1, sizeof(dp));
    int ans = calc(3, a[1], a[2]);
    cout << ans << '\n';
  }
}
signed main(){
  int t=1;
  while(t--)Solve();
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 56 ms 111340 KB Output is correct
4 Correct 58 ms 111488 KB Output is correct
5 Correct 56 ms 111340 KB Output is correct
6 Correct 56 ms 111340 KB Output is correct
7 Correct 57 ms 111468 KB Output is correct
8 Correct 59 ms 111340 KB Output is correct
9 Correct 59 ms 111468 KB Output is correct
10 Correct 62 ms 111596 KB Output is correct
11 Correct 72 ms 112620 KB Output is correct
12 Correct 62 ms 111724 KB Output is correct
13 Correct 74 ms 112748 KB Output is correct
14 Correct 88 ms 113388 KB Output is correct
15 Correct 158 ms 115692 KB Output is correct
16 Correct 154 ms 115592 KB Output is correct
17 Correct 213 ms 116972 KB Output is correct
18 Correct 206 ms 116844 KB Output is correct
19 Correct 192 ms 116588 KB Output is correct
20 Correct 215 ms 117100 KB Output is correct