Cod sursa(job #2027403)
| Utilizator | Data | 26 septembrie 2017 01:42:34 | |
|---|---|---|---|
| Problema | Heavy metal | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.58 kb |
#include <bits/stdc++.h>
#define a first
#define b second
using namespace std;
ifstream F("heavymetal.in");
ofstream G("heavymetal.out");
int n, st, dr, mij, Tm, x, y;
long long dp[1<<18];
vector<int> w[1<<18];
int main()
{
F >> n;
for(int i = 1; i <= n; ++ i) {F >> x >> y, w[y].push_back(x); Tm=max(Tm, y);}
vector<int>::iterator it;
for(int i = 1; i <= Tm; ++ i)
{
dp[i]=dp[i-1];
for(it=w[i].begin(); it!=w[i].end();++it)
if(dp[i]<dp[*it]+i-(*it)) dp[i]=dp[*it]+i-(*it);
}
G<<dp[Tm];
return 0;
}
