Pagini recente » Cod sursa (job #1626052) | Cod sursa (job #2377216) | Cod sursa (job #1858912) | Cod sursa (job #1706982) | Cod sursa (job #1401315)
#include<iostream>
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int dp[2][100005];
vector <pair <int,int> > a;
int n;
void citire()
{
int i,x,y;
f>>n;
for(i=1;i<=n;i++){
f>>x>>y;
a.push_back(make_pair(y,x));
}
sort(a.begin(),a.end());
}
void rez()
{
int i,j,durata,orai,oraf;
dp[0][1] = a[0].first - a[0].second;
dp[1][1] = a[0].first;
for(i=2; i<=n; i++){
orai = a[i-1].second;
oraf = a[i-1].first;
durata = a[i-1].first - a[i-1].second;
for(j=i-1; j>0 && dp[1][j] > orai; j--);
if(dp[0][i-1] > dp[0][j] + durata){
dp[1][i] = dp[1][i-1];
dp[0][i] = dp[0][i-1];
}
else{
dp[1][i] = oraf;
dp[0][i] = dp[0][j] + durata;
}
}
g<<dp[0][n]<<"\n";
}
int main()
{
citire();
rez();
return 0;
}