Pagini recente » Cod sursa (job #601809) | Cod sursa (job #2372447) | Cod sursa (job #1493667) | Cod sursa (job #585298) | Cod sursa (job #389122)
Cod sursa(job #389122)
# include <fstream>
# include <algorithm>
using namespace std;
struct nod {
int i, j;};
int n, l[100003], lmax;
nod f[100003];
void read ()
{
ifstream fin ("heavymetal.in");
fin>>n;
int x, y;
for (int i=1;i<=n;i++)
{
fin>>x>>y;
f[i].i=x;
f[i].j=y;
}
}
bool fcmp (nod i, nod j)
{
if (i.i<j.i)return 1;
if (i.i==j.i && i.j<=j.j) return 1;
return 0;
}
void dnmc ()
{
for (int i=1;i<=n;i++)
l[i]=f[i].j-f[i].i;
for (int i=1;i<=n;i++)
for (int j=i-1;j;j--)
if (f[j].j<=f[i].i && l[j]+(f[i].j-f[i].i)>l[i])
{
l[i]=l[j]+(f[i].j-f[i].i);
if (l[i]>lmax)
lmax=l[i];
}
}
int main ()
{
read ();
sort (f+1, f+n+1, fcmp);
dnmc ();
ofstream fout ("heavymetal.out");
fout<<lmax;
return 0;
}