백준(BOJ) 16169 수행시간 *

# DP

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n;
pair<int, int> node[101];
vector<int> v[102];
int ans;
int dp[101];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &node[i].first, &node[i].second);
		v[node[i].first].push_back(i);
	}
	for (int i = 1; i <= n; i++)
	{
		if (v[i].empty() == true)
			continue;
		if (v[i + 1].empty() == true)
		{
			for (auto & j : v[i])
			{
				int tmp = dp[j] + node[j].second;
				ans = max(ans,tmp);
			}
			continue;
		}
		for (auto & j : v[i])
		{
			for (auto & k : v[i + 1])
			{
				dp[k] = max(dp[k], dp[j] + node[j].second + (k - j)*(k - j));
				ans = max(ans, dp[k]);
			}
		}
	}
	printf("%d", ans);
	return 0;
}