Cod sursa(job #2054553)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 2 noiembrie 2017 09:03:48
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define max(a, b) a>b?a:b
#define N 100005

using namespace std;

int n, ind[N], din[N];
struct timp
{
    int st, fin, dur;
}a[N];

void citire()
{
    scanf("%d\n", &n);
    for(int i=1;i<=n;i++)
        scanf("%d %d\n", &a[i].st, &a[i].fin), a[i].dur=a[i].fin-a[i].st, ind[i]=i;
}

void sortare(int ind[], int st, int dr)
{
    int i=st, j=dr;
    int pivot=ind[(st+dr)/2];
    while(i<=j)
    {
        while(a[ind[i]].st<a[pivot].st)
            i++;
        while(a[ind[j]].st>a[pivot].st)
            j--;
        if(i<=j)
        {
            int aux=ind[i];
            ind[i]=ind[j];
            ind[j]=aux;
            i++;
            j--;
        }
      }
      if(st<j)
        sortare(ind, st, j);
      if(i<dr)
        sortare(ind, i, dr);
}

int caut(int x, int st, int dr)
{
    if(a[ind[st]].fin==x)
        return ind[st];

    int mij=(st+dr)/2;
    if(x>a[ind[mij]].fin)
        return caut(x, mij+1, dr);
    return caut(x, st, mij);
}

void calcul()
{
    for(int i=1;i<=a[ind[n]].fin;i++)
    {
        din[i]=din[i-1];
        for(int j=1;j<=n;j++)
            if(a[ind[j]].fin==i)
                din[i]=max(din[i], din[a[ind[j]].st]+a[ind[j]].dur);
            else
                if(a[ind[j]].fin>i)
                    break;
    }
}

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    citire();
    sortare(ind, 1, n);
    calcul();
    printf("%d", din[a[ind[n]].fin]);
    return 0;
}