Cod sursa(job #1867036)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 3 februarie 2017 17:59:18
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
#define nmax 100005

using namespace std;

struct numere
{
    int st;
    int dr;
}num[nmax];

int n;
int dinamica[nmax];

bool cmp(numere a, numere b)
{
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}
int find_k(numere x[nmax], int s, int start, int current)
{
    int i;
    for(i=start;i<current-1&&x[i+1].dr<=s;i++);
    return i;
}

void citire()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        int s, d;
        scanf("%d%d", &s, &d);
        num[i].st=s;
        num[i].dr=d;
    }
}
void rezolvare()
{
    sort(num+1, num+n+1, cmp);
    dinamica[1]=num[1].dr-num[1].st;
    int last_k=1;
    for(int i=2;i<=n;i++)
    {
        int k;
        k=find_k(num, num[i].st, last_k, i);
        last_k=k;
        dinamica[i]=num[i].dr-num[i].st+dinamica[k];
    }
}
void afisare()
{
    printf("%d\n", dinamica[n]);
}

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

    citire();
    rezolvare();
    afisare();

    return 0;
}