Submission #572413

#	Time	Username	Problem	Language	Result	Execution time	Memory
572413		SSRS	Skyline (IZhO11_skyline)	C++14	100 / 100	108 ms	50188 KiB

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 / 100