Processing math: 100%
[Codewars] Alice`s christmas tree

Alice’s christmas tree

  • Time : O(nlogn+nk)
  • Space : O(k)
c++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int largest_visible_area(int k, std::vector<std::pair<int, int>> cylinders) {
vector<int> dp(k, INT_MIN); dp[0] = 0;
sort(rbegin(cylinders), rend(cylinders));
for(int i = 0; i < cylinders.size(); i ++) {
auto [r,m] = cylinders[i];
if(i and cylinders[i-1].first == r) continue;
for(int j = k-1; j >= 1; j--) dp[j] = max(dp[j], dp[j-1] + m);
dp[0] = max(dp[0], r * r + m);
}
return dp[k-1];
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2023/06/08/PS/Codewars/alices-christmas-tree/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.

Related Issues not found

Please contact @SongHayoung to initialize the comment