Cod sursa(job #731303)

Utilizator vendettaSalajan Razvan vendetta Data 7 aprilie 2012 21:16:17
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <algorithm>
#define nmax 100005

using namespace std;

int n, dp[nmax][3];
pair<int,int> v[nmax];

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

bool cmp(pair<int,int> a, pair<int,int> b){

    if (a.second == b.second){
        /*
        int x = a.second - a.first;
        int y = b.second - b.first;
        */
        return a.first > b.first;
    }

    return a.second < b.second;

}

void citeste(){

    f >> n;

    for(int i=1; i<=n; i++){
        int x,y;
        f >> x >> y;
        v[i]=(make_pair(y-x, y));
    }

    sort(v+1, v+n+1, cmp);

}

void rezolva(){

    for(int i=1; i<=n; i++){
        int val = v[i].first;//am durata concertului
        int final = v[i].second;
        int start = final - val;
        dp[i][0] = val;
        dp[i][1] = final;
        //g << val << " " << start << "\n";
        int Max = 0;
        for(int j=1; j<i; j++){
            if (start >= dp[j][1]){//daca pot continua un concert
                Max = max(Max, dp[j][0]);
            }
        }
        dp[i][0] = Max+val;
    }

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

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}