Cod sursa(job #2049474)

Utilizator VladAfrasineiAfrasinei VladAfrasinei Data 27 octombrie 2017 11:48:47
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda hlo2017_cj_av_l4 Marime 1.08 kb
#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;
}