Submission #1000348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000348		MilosMilutinovic	Skyline (IZhO11_skyline)	C++14	100 / 100	840 ms	936 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++) {
          for (int two = min({x - a, y - b}) - three; two <= min({x - a, y - b}) - three; two++) {
            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);
          }
        }
        /* int ta = a, tb = b, tc = 0;
        int ft = dp[a][b];
        {
          int v = min({x - ta, y - tb, h[i] - tc});
          ta += v;
          tb += v;
          tc += v;
          ft += 7 * v;
        }
        {
          int v = min({x - ta, y - tb});
          ta += v;
          tb += v;
          ft += 5 * v;
        }
        {
          int v = x - ta;
          ta += v;
          ft += 3 * v;
        }
        new_dp[tb][tc] = min(new_dp[tb][tc], ft); */
      } 
    }
    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