TIMBER - hackercup problem C

editorial
, ,
1

problem link
Can anyone provide me detailed explanation and code for this problem ?
Thanks in advance !

2

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

}