Cod sursa(job #1431067)

Utilizator cruceru_vlad_ionut_321CACruceru Vlad - Ionut 321CA cruceru_vlad_ionut_321CA Data 8 mai 2015 23:24:14
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

struct comp
{
    bool operator() (const vector<int> & a,
            const vector<int> & b)
    { return a[1] < b[1];}
} mycomp;

int best[100001];

int main()
{
    ifstream f("heavymetal.in");
    ofstream g("heavymetal.out");
    int N;
    f >> N;
    vector<vector<int> > inte(N, vector<int> (2, 0));
    for(int i = 0; i < N; i++)
    {
        int a, b;
        f >> a >> b;
        inte[i][0] = a;
        inte[i][1] = b;
    }
    sort (inte.begin(), inte.end(), mycomp);

    int j = 0;
    best[0] = 0;
    for(int i = 1; i <= inte[N - 1][1]; i++)
    {
        if (j == N)
        {
            best[inte[N - 1][1]] = best[i - 1];
            break;
        }
        if(inte[j][1] < i)
        {
            j++;
            i--;
            continue;
        }
        else if (inte[j][1] > i)
        {
            best[i] = best[i - 1];
            continue;
        }
        else
        {
            best[i] = max(best[i], best[i - 1]);
            best[i] = max(best[i],
                        best[inte[j][0]] +
                        (inte[j][1] - inte[j][0]));
            j++;
            if (j == N)
            {
                best[inte[N - 1][1]] = best[i];
                break;
            }
            if(inte[j][1] == i)
                i--;
        }
    }
    g << best[inte[N - 1][1]];

    f.close();
    g.close();
    return 0;
}