Cod sursa(job #1401315)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 25 martie 2015 19:43:26
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

int dp[2][100005];
vector <pair <int,int> > a;
int n;

void citire()
{
    int i,x,y;
    f>>n;
    for(i=1;i<=n;i++){
        f>>x>>y;
        a.push_back(make_pair(y,x));
    }
    sort(a.begin(),a.end());
}


void rez()
{
    int i,j,durata,orai,oraf;

    dp[0][1] = a[0].first - a[0].second;
    dp[1][1] = a[0].first;

    for(i=2; i<=n; i++){

        orai = a[i-1].second;
        oraf = a[i-1].first;
        durata = a[i-1].first - a[i-1].second;

        for(j=i-1; j>0 && dp[1][j] > orai; j--);

        if(dp[0][i-1] > dp[0][j] + durata){
            dp[1][i] = dp[1][i-1];
            dp[0][i] = dp[0][i-1];
        }
        else{
            dp[1][i] = oraf;
            dp[0][i] = dp[0][j] + durata;
        }
    }

    g<<dp[0][n]<<"\n";
}

int main()
{
    citire();
    rez();
    return 0;
}