oj.uz

Submission #548366

# Submission time Handle Problem Language Result Execution time Memory
548366 2022-04-13T06:41:37 Z Soumya1 Skyline (IZhO11_skyline) C++17
100 / 100
 116 ms 736 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 301;
const int mxH = 201;
const int inf = 1e9;
int h[mxN];
void testCase() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> h[i];
  vector<vector<int>> dp(mxH, vector<int> (mxH, inf));
  for (int i = h[1]; i >= 0; i--) {
    dp[0][i] = (h[1] - i) * 3;
  }
  for (int i = 2; i <= n; i++) {
    vector<vector<int>> new_dp(mxH, vector<int> (mxH, inf));
    for (int cur = 0; cur <= h[i]; cur++) {
      for (int last = 0; last <= h[i - 1]; last++) {
        if (last + h[i] - cur <= h[i - 1]) {
          new_dp[last][cur] = min(new_dp[last][cur], dp[h[i] - cur][last + h[i] - cur] + (h[i] - cur) * 7);
        }
      }
    }
    dp = new_dp;
    for (int cur = h[i]; cur >= 0; cur--) {
      for (int last = h[i - 1]; last >= 0; last--) {
        if (last - 1 >= 0) {
          dp[last - 1][cur] = min(dp[last - 1][cur], dp[last][cur] + 3);
        }
        if (cur - 1 >= 0 && last - 1 >= 0) {
          dp[last - 1][cur - 1] = min(dp[last - 1][cur - 1], dp[last][cur] + 5);
        }
        if (cur - 1 >= 0) {
          dp[last][cur - 1] = min(dp[last][cur - 1], dp[last][cur] + 3);
        }
      }
    }
  }
  cout << dp[0][0] << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 652 KB Output is correct
11 Correct 16 ms 648 KB Output is correct
12 Correct 4 ms 648 KB Output is correct
13 Correct 17 ms 652 KB Output is correct
14 Correct 29 ms 676 KB Output is correct
15 Correct 81 ms 652 KB Output is correct
16 Correct 76 ms 736 KB Output is correct
17 Correct 108 ms 648 KB Output is correct
18 Correct 104 ms 720 KB Output is correct
19 Correct 104 ms 652 KB Output is correct
20 Correct 116 ms 648 KB Output is correct