Submission #1000346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000346	2024-06-17T09:45:08 Z	MilosMilutinovic	Skyline (IZhO11_skyline)	C++14	0 / 100	2000 ms	848 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 = 0; 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

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	1 ms	604 KB	Output is correct
4	Correct	1 ms	784 KB	Output is correct
5	Correct	1 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	5 ms	776 KB	Output is correct
9	Correct	26 ms	792 KB	Output is correct
10	Correct	86 ms	776 KB	Output is correct
11	Correct	404 ms	776 KB	Output is correct
12	Correct	280 ms	744 KB	Output is correct
13	Correct	519 ms	848 KB	Output is correct
14	Correct	1378 ms	760 KB	Output is correct
15	Execution timed out	2072 ms	748 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-