Cod sursa(job #1099513)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 5 februarie 2014 21:37:46
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;

struct formatie {int start;int sfarsit;};
formatie trupa[100010];
int n,dp[100010];

bool cmp(formatie A,formatie B) {
    return A.sfarsit<B.sfarsit;
}

void citire() {

    ifstream in("heavymetal.in");
    int i;
    in>>n;
    for(i=1;i<=n;i++)
        in>>trupa[i].start>>trupa[i].sfarsit;

    in.close();

}

int cautbin(int lol) {

    int st,dr,m;
    st=0;
    dr=lol;
    while(st<=dr) {
        m=(st+dr)/2;
        if(trupa[m].sfarsit>trupa[lol].start)
            dr=m-1;
        else
            st=m+1;
    }
    m=(st+dr)/2;
    return m;
}

void solve() {

    int i,maxim,a,poz;
    sort(trupa+1,trupa+n+1,cmp);
    dp[1]=trupa[1].sfarsit-trupa[1].start;
    maxim=dp[1];
    for(i=2;i<=n;i++) {
        poz=cautbin(i);
        a=trupa[i].sfarsit-trupa[i].start;
        if(dp[poz]+a>maxim) {
            maxim=dp[poz]+a;
            dp[i]=dp[poz]+a;
        }
        else
            dp[i]=maxim;
    }
}

void afisare() {

    ofstream out("heavymetal.out");
    int i;
    out<<dp[n];
    out.close();

}

int main () {

    citire();
    solve();
    afisare();
    return 0;

}