oj.uz

Submission #1000349

# Submission time Handle Problem Language Result Execution time Memory
1000349 2024-06-17T09:48:55 Z MilosMilutinovic Skyline (IZhO11_skyline) C++14
100 / 100
 608 ms 876 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 776 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 1 ms 776 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 1 ms 772 KB Output is correct
10 Correct 2 ms 772 KB Output is correct
11 Correct 8 ms 780 KB Output is correct
12 Correct 5 ms 776 KB Output is correct
13 Correct 14 ms 784 KB Output is correct
14 Correct 31 ms 788 KB Output is correct
15 Correct 294 ms 776 KB Output is correct
16 Correct 307 ms 820 KB Output is correct
17 Correct 608 ms 772 KB Output is correct
18 Correct 539 ms 776 KB Output is correct
19 Correct 472 ms 876 KB Output is correct
20 Correct 541 ms 772 KB Output is correct