problem link
Can anyone provide me detailed explanation and code for this problem ?
Thanks in advance !
Sorry, don’t have time to explain. I think the solutions are posted on the FB HackerCup page though.
void solve()
{
ll n, p, h;
scan(n);
vector<pair<ll, ll>> points(n);
for (ll i = 0; i < n; ++i)
{
scan(points[i].first); scan(points[i].second);
}
// sorting points by position
sort(points.begin(), points.end(),
[](const pair<ll, ll>& point1, const pair<ll, ll>& point2)
{return point1.first < point2.first;}
);
map<ll, ll> dp; // Maps positions to length of timber interval
for (ll i = 0; i < n; ++i)
{
p = points[i].first;
h = points[i].second;
dp[p + h] = max(dp[p + h], dp[p] + h);
dp[p] = max(dp[p - h] + h, dp[p]);
}
// finding the length of largest timber interval
auto maxx = *max_element(dp.begin(), dp.end(),
[](const pair<ll, ll>& point1, const pair<ll, ll>& point2)
{return point1.second < point2.second;}
);
pnl(maxx.second); // pnl - print followed by line feed
}