제출 #1000349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000349		MilosMilutinovic	스카이라인 (IZhO11_skyline)	C++14	100 / 100	608 ms	876 KiB

skyline

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  if (n == 1) {
    cout << 3 * h[0] << '\n';
    return 0;
  }
  const int MAX = 202;
  const int inf = (int) 1e9;
  vector<vector<int>> dp(MAX, vector<int>(MAX, inf));
  dp[0][0] = 0;
  for (int i = 0; i < n; i++) {
    int x = (i >= 2 ? h[i - 2] : 0);
    int y = (i >= 1 ? h[i - 1] : 0);
    vector<vector<int>> new_dp(MAX, vector<int>(MAX, inf));
    for (int a = 0; a <= x; a++) {
      for (int b = 0; b <= y; b++) {
        if (dp[a][b] == inf) {
          continue;
        }
        for (int three = 0; three <= min({x - a, y - b, h[i]}); three++) {
          int two = min({x - a, y - b}) - three;
          int ta = a + three + two;
          int tb = b + three + two;
          int tc = three;
          new_dp[tb][tc] = min(new_dp[tb][tc], dp[a][b] + three * 7 + two * 5 + (x - ta) * 3);
        }
      } 
    }
    swap(dp, new_dp);
  }
  int res = inf;
  int x = h[n - 2];
  int y = h[n - 1];
  for (int a = 0; a <= x; a++) {
    for (int b = 0; b <= y; b++) {
      if (dp[a][b] == inf) {
        continue;
      }
      int ta = a, tb = b;
      int ft = dp[a][b];
      {
        int v = min({x - ta, y - tb});
        ta += v;
        tb += v;
        ft += 5 * v;
      }
      {
        int v = max({x - ta, y - tb});
        ft += 3 * v;
      }
      res = min(res, ft);
    }
  }
  cout << res << '\n';
  return 0;
}

• Subtask 1: 100 / 100