oj.uz

Submission #523518

# Submission time Handle Problem Language Result Execution time Memory
523518 2022-02-07T18:01:45 Z Pety Skyline (IZhO11_skyline) C++14
0 / 100
 55 ms 48232 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 = min(v[i], min(v[i + 1], v[i - 1])); j >= 0; 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 27 ms 48204 KB Output is correct
2 Correct 28 ms 48204 KB Output is correct
3 Correct 27 ms 48144 KB Output is correct
4 Correct 30 ms 48204 KB Output is correct
5 Correct 27 ms 48204 KB Output is correct
6 Correct 28 ms 48204 KB Output is correct
7 Correct 30 ms 48152 KB Output is correct
8 Correct 31 ms 48088 KB Output is correct
9 Correct 29 ms 48168 KB Output is correct
10 Correct 27 ms 48120 KB Output is correct
11 Correct 32 ms 48124 KB Output is correct
12 Correct 28 ms 48232 KB Output is correct
13 Correct 32 ms 48192 KB Output is correct
14 Correct 35 ms 48108 KB Output is correct
15 Incorrect 55 ms 48224 KB Output isn't correct
16 Halted 0 ms 0 KB -