Submission #572413

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
572413	2022-06-04T10:43:35 Z	SSRS	Skyline (IZhO11_skyline)	C++14	100 / 100	108 ms	50188 KB

skyline

#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
int main(){
  int N;
  cin >> N;
  vector<int> h(N);
  for (int i = 0; i < N; i++){
    cin >> h[i];
  }
  vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(201, vector<int>(201, INF)));
  dp[0][0][0] = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j <= h[i]; j++){
      for (int k = j; k <= 200; k++){
        dp[i + 1][k - j][h[i] - j] = min(dp[i + 1][k - j][h[i] - j], dp[i][j][k] + j * 7);
      }
    }
    for (int j = 200; j >= 0; j--){
      for (int k = 199; k >= 0; k--){
        if (j < 200){
          dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i + 1][j + 1][k + 1] + 5);
        }
        dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i + 1][j][k + 1] + 3);
      }
    }
  }
  cout << dp[N][0][0] << endl;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	828 KB	Output is correct
2	Correct	1 ms	940 KB	Output is correct
3	Correct	2 ms	1364 KB	Output is correct
4	Correct	21 ms	12116 KB	Output is correct
5	Correct	2 ms	1584 KB	Output is correct
6	Correct	3 ms	2260 KB	Output is correct
7	Correct	3 ms	2004 KB	Output is correct
8	Correct	3 ms	1748 KB	Output is correct
9	Correct	5 ms	2772 KB	Output is correct
10	Correct	8 ms	4564 KB	Output is correct
11	Correct	46 ms	23908 KB	Output is correct
12	Correct	10 ms	5676 KB	Output is correct
13	Correct	54 ms	28040 KB	Output is correct
14	Correct	68 ms	33496 KB	Output is correct
15	Correct	106 ms	45976 KB	Output is correct
16	Correct	88 ms	41356 KB	Output is correct
17	Correct	106 ms	50104 KB	Output is correct
18	Correct	108 ms	49748 KB	Output is correct
19	Correct	105 ms	48012 KB	Output is correct
20	Correct	105 ms	50188 KB	Output is correct