Pagini recente » Cod sursa (job #2613033) | Cod sursa (job #2406275) | Cod sursa (job #728488) | Cod sursa (job #1160654) | Cod sursa (job #2049474)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n;
struct elem
{
int s,d;
};
elem a[100001];
int t[100001],p[100001];
bool cmp(elem x1,elem x2)
{
if(x1.d<x2.d)
return 1;
if(x1.d==x2.d&&x1.s<x2.s)
return 1;
return 0;
}
int main()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i].s>>a[i].d;
sort(a+1,a+n+1,cmp);
t[1]=a[1].d-a[1].s;
p[1]=1;
for(i=2;i<=n;i++)
if(a[i].s>=a[i-1].d)
{t[i]=a[i].d-a[i].s+t[i-1];
p[i]=i;
}
else
if(a[i].d<=a[i-1].d)
{
t[i]=t[i-1];
p[i]=p[i-1];
}
else
{
if(t[i-1]>=(t[i-1]+a[i].d-a[i].s-(a[p[i-1]].d-a[p[i-1]].s)))
{
t[i]=t[i-1];
p[i]=p[i-1];
}
else
{
t[i]=t[i-1]+a[i].d-a[i].s-(a[p[i-1]].d-a[p[i-1]].s);
p[i]=i;
}
}
fout<<t[n];
return 0;
}