Pagini recente » Cod sursa (job #612606) | Cod sursa (job #2825605) | Cod sursa (job #2929267)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct concert {
int beg;
int end;
concert()
{
beg = 0;
end = 0;
}
void afisare()
{
fout << beg << " " << end << endl;
}
}v[100001];
struct position {
int indice;
int suma;
position()
{
indice = 0;
suma = 0;
}
void afisare()
{
fout << indice << " " << suma << endl;
}
}poz[100001];
bool compare(concert a, concert b)
{
if (a.end < b.end)
return 1;
else if (a.end == b.end)
if (a.beg < b.beg)
return 1;
return 0;
}
int main()
{
int n;
fin >> n;
for (int i{ 1 }; i <= n; i++)
fin >> v[i].beg >> v[i].end;
sort(v + 1, v + n + 1, compare);
int sum = 0, m = 0;
for (int i = 1; i <= n; i++)
if (v[i].beg >= v[poz[m].indice].end)
{
m++;
sum += (v[i].end - v[i].beg);
poz[m].indice = i;
poz[m].suma = sum;
}
else
{
for (int j = 0; j < m; j++)
if (v[i].beg <= v[poz[j + 1].indice].beg && v[i].beg >= v[poz[j].indice].end && (v[i].end - v[i].beg) >= poz[j + 1].suma)
{
sum += ((v[i].end - v[i].beg) - (poz[m].suma - poz[j].suma));
m = j + 1;
poz[m].indice = i;
poz[m].suma = sum;
break;
}
}
fout << sum;
return 0;
}
/* int poz = 0, sum = 0, prev = 0;
for (int i{ 1 }; i <= n; i++)
if (v[i].beg >= v[poz].end)
{
sum += (v[i].end - v[i].beg);
prev = poz;
poz = i;
}
else if (v[i].beg >= v[prev].end && (v[i].end - v[i].beg) > (v[poz].end - v[poz].beg))
{
sum += ((v[i].end - v[i].beg) - (v[poz].end - v[poz].beg));
poz = i;
}
cout << sum;
*/