Submission #339534

#	Time	Username	Problem	Language	Result	Execution time	Memory
339534		tengiz05	Skyline (IZhO11_skyline)	C++17	100 / 100	215 ms	117100 KiB

skyline

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