Submission #523505

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523505	2022-02-07T17:51:40 Z	Pety	Skyline (IZhO11_skyline)	C++14	0 / 100	51 ms	48268 KB

skyline

#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 = 0; k <= v[i - 1]; k++) {
        dp[i][j][k] = min(dp[i][j + 1][k] + 3, dp[i][j][k]);
        dp[i][j][k] = min(dp[i][j + 1][k + 1] + 5, dp[i][j][k]);
      }
    for (int j = 0; j <= min(v[i], min(v[i + 1], v[i - 1])); j++)
      for (int k = v[i + 1]; 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	29 ms	48168 KB	Output is correct
2	Correct	28 ms	48116 KB	Output is correct
3	Correct	37 ms	48200 KB	Output is correct
4	Correct	29 ms	48168 KB	Output is correct
5	Correct	37 ms	48100 KB	Output is correct
6	Correct	28 ms	48132 KB	Output is correct
7	Correct	28 ms	48196 KB	Output is correct
8	Correct	29 ms	48096 KB	Output is correct
9	Correct	29 ms	48120 KB	Output is correct
10	Correct	31 ms	48124 KB	Output is correct
11	Correct	33 ms	48268 KB	Output is correct
12	Correct	29 ms	48212 KB	Output is correct
13	Correct	33 ms	48196 KB	Output is correct
14	Correct	35 ms	48196 KB	Output is correct
15	Incorrect	51 ms	48196 KB	Output isn't correct
16	Halted	0 ms	0 KB	-