Pagini recente » Cod sursa (job #3269697) | Winter Challenge 2008 | Cod sursa (job #493496) | Cod sursa (job #669816) | Cod sursa (job #2965992)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N = 100000;
struct trupa{
int st, dr;
};
trupa v[N + 1];
int n, t[N + 1];
///t[i] = timpul maxim pentru intervalul care se termina in v[i].fn
bool cmp(trupa a, trupa b)
{
return a.dr < b.dr;
}
int caut_bin(int poz)
{
int st = 1, dr = n, last = 0;
while (st <= dr)
{
int mij = (st + dr) / 2;
if (v[mij].dr <= v[poz].st)
{
///out << "\n" << "pentru trupa " << poz << " last-ul este " << last << " si are timpul " << v[last].dr - v[last].st << " si potentialul last este " << mij;
if (v[mij].dr - v[mij].st >= v[last].dr - v[last].st)
{
last = mij;
}
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
return last;
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++)
{
in >> v[i].st >> v[i].dr;
}
sort(v + 1, v + n + 1, cmp);
t[0] = 0;
/**for (int i = 1; i <= n; i++)
{
out << v[i].st << " " << v[i].dr << "\n";
}
*/
for (int i = 1; i <= n; i++)
{
///caut binar cel mai bun interval cu v[k].dr <= v[i].st
int ind = caut_bin(i);
t[i] = t[ind] + (v[i].dr - v[i].st);
///out << "\n" << "am ajuns la trupa " << i << " pentru care cel mai bun interval este cel de pe pozitia " << ind << " si care are t-ul egal cu " << t[i] << ' ' << "\n";
}
out << t[n];
return 0;
}