Submission #1000348

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000348	2024-06-17T09:48:14 Z	MilosMilutinovic	Skyline (IZhO11_skyline)	C++14	100 / 100	840 ms	936 KB

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.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	784 KB	Output is correct
5	Correct	0 ms	604 KB	Output is correct
6	Correct	1 ms	776 KB	Output is correct
7	Correct	1 ms	776 KB	Output is correct
8	Correct	0 ms	776 KB	Output is correct
9	Correct	1 ms	776 KB	Output is correct
10	Correct	4 ms	776 KB	Output is correct
11	Correct	11 ms	776 KB	Output is correct
12	Correct	6 ms	780 KB	Output is correct
13	Correct	18 ms	788 KB	Output is correct
14	Correct	45 ms	784 KB	Output is correct
15	Correct	455 ms	776 KB	Output is correct
16	Correct	444 ms	780 KB	Output is correct
17	Correct	825 ms	776 KB	Output is correct
18	Correct	745 ms	936 KB	Output is correct
19	Correct	679 ms	776 KB	Output is correct
20	Correct	840 ms	772 KB	Output is correct