oj.uz

Submission #523516

# Submission time Handle Problem Language Result Execution time Memory
523516 2022-02-07T17:59:59 Z Pety Skyline (IZhO11_skyline) C++14
0 / 100
 49 ms 48228 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, v[302], dp[302][202][202];

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> v[i];
  for (int i = 1; i <= 300; i++)
    for (int j = 0; j <= 200; j++)
      for (int k = 0; k <= 200; k++)
        dp[i][j][k] = INF;
      
  for (int i = 0; i <= v[1]; i++)
    dp[2][v[2]][i] = dp[1][i][0] = 3 * (v[1] - i);
  for (int i = 2; i <= n; i++) {
      for (int j = v[i]; j >= 0; j--)
        for (int k = v[i - 1]; k >= 0; k--) 
          dp[i][j][k] = min(dp[i][j + 1][k] + 3, dp[i][j][k]);
        
      for (int j = v[i]; j >= 0; j--)
        for (int k = v[i - 1]; k >= 0; k--) 
          dp[i][j][k] = min(dp[i][j + 1][k + 1] + 5, dp[i][j][k]);
    if (i == n)
      continue;
    for (int j = 0; j <= min(v[i], min(v[i + 1], v[i - 1])); j++)
      for (int k = v[i]; k >= j; k--)
        dp[i + 1][v[i + 1] - j][k - j] = min(dp[i + 1][v[i + 1] - j][k - j], dp[i][k][j] + 7 * j);
  }
  cout << dp[n][0][0];
  return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48204 KB Output is correct
2 Correct 26 ms 48100 KB Output is correct
3 Correct 28 ms 48204 KB Output is correct
4 Correct 28 ms 48192 KB Output is correct
5 Correct 32 ms 48148 KB Output is correct
6 Correct 29 ms 48204 KB Output is correct
7 Correct 35 ms 48164 KB Output is correct
8 Correct 29 ms 48100 KB Output is correct
9 Correct 28 ms 48104 KB Output is correct
10 Correct 28 ms 48136 KB Output is correct
11 Correct 31 ms 48136 KB Output is correct
12 Correct 28 ms 48228 KB Output is correct
13 Correct 31 ms 48204 KB Output is correct
14 Correct 34 ms 48144 KB Output is correct
15 Incorrect 49 ms 48208 KB Output isn't correct
16 Halted 0 ms 0 KB -