Cod sursa(job #983779)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 12 august 2013 18:11:00
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
// caz particular al problemei rent de pe spoj?
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int n,m, Max;
struct order{ int s,f,c;};
struct vect {int final, cost;};
int A[10005],q;
order a[10005];
inline int cmp(order a, order b)
{
    if (a.f>b.f)
        return 0;
    return 1;
}
void sorteaza_chestia_asta()
{
    sort(a+1,a+1+n,cmp);
}
int cauta_bin_un_indice_bun(int nr, int m)
{


    int *p = upper_bound(A+1, A + m+1, nr);
    return p-A-1;
}
int main()
{
    int i,t,z,ind,costc;
    fstream f,g;
    f.open("heavymetal.in",ios::in);
    g.open("heavymetal.out",ios::out);
    //f>>t;
    t=1;
    while (t--)
    {
        f>>n;
        for (i=1;i<=n;i++)
        {
            f>>a[i].s;
            f>>a[i].f;
            a[i].c=a[i].f-a[i].s;
        }
        sorteaza_chestia_asta();
        A[1]=a[1].f;
        Max=a[1].c;
        for (i=2;i<=n;i++)
        {
            A[i]=a[i].f;
            ind=cauta_bin_un_indice_bun(a[i].s,i);
            a[i].c+=a[ind].c;
            Max=max(Max,a[i].c);
            a[i].c=Max;
        }
        g<<a[n].c<<' ';
    }
}