Pagini recente » Borderou de evaluare (job #156731) | Cod sursa (job #2295876) | Cod sursa (job #867031) | Cod sursa (job #1385018) | Cod sursa (job #1123100)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define maxim(a,b) ((a>b)?(a):(b))
int N;
int Tmax;
vector < int > DP;
vector < pair < int , int > > I;
void Scannen()
{
freopen("heavymetal.in","r",stdin);
scanf("%d",&N);
for(int i=1,x,y;i<=N;i++)
{
scanf("%d%d",&x,&y);
I.push_back(make_pair(y,x));
}
}
void Losen()
{
sort(I.begin(),I.end());
Tmax = I[N-1].first;
DP.resize(Tmax + 1);
for(int i=1; i<=Tmax; i++)
{
DP[i] = DP[i-1];
vector < pair < int , int > > :: iterator it = I.begin();
for(;(*it).first < i; ++it);
for(;(*it).first == i; ++it)
DP[i] = maxim(DP[i], DP[(*it).second] + (*it).first - (*it).second);
}
}
void Druken()
{
freopen("heavymetal.out", "w", stdout);
printf("%d\n", DP[Tmax]);
}
int main()
{
Scannen();
Losen();
Druken();
return 0;
}