Cod sursa(job #1397008)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 23 martie 2015 10:52:50
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

struct pii
{
	int lo, hi;
    pii(int _lo, int _hi)
    {
    	lo = _lo;
    	hi = _hi;
    }
    bool operator< (const pii& rhs) const
    {
    	if (hi != rhs.hi)
			return (hi < rhs.hi);
		return (lo < rhs.lo);
    }
};

int n;
vector<int> dp, a, b;
vector<pii> p;


void read()
{
	ifstream fin("heavymetal.in");
	fin >> n;
	for (int i = 1; i <= n; ++i)
	{
		int x, y;
		fin >> x >> y;
        p.push_back(pii(x, y));
	}
	fin.close();
}

void write()
{
	ofstream fout("heavymetal.out");
	fout << dp[n - 1] << '\n';
	fout.close();
}

void findMaxTime()
{
	sort(p.begin(), p.end());

	for (size_t i = 0; i < p.size(); ++i)
	{
		a.push_back(p[i].lo);
		b.push_back(p[i].hi);
		dp.push_back(0);
	}

	dp[0] = b[0] - a[0];
    for (int i = 1; i < n; ++i)
	{
        dp[i] = dp[i - 1];
        vector<int>::iterator it = lower_bound(b.begin(), b.begin() + i, a[i]);

        if ((*it) > a[i])
		{
			if (it == b.begin())
				continue;
			else
				--it;
		}

		int j = distance(b.begin(), it);
		dp[i] = max(dp[i], dp[j] + b[i] - a[i]);
	}
}


int main()
{
	read();
	findMaxTime();
	write();
	return 0;
}