Pagini recente » Cod sursa (job #956301) | Cod sursa (job #2904082) | Cod sursa (job #69820) | Cod sursa (job #2301967) | Cod sursa (job #983779)
Cod sursa(job #983779)
// caz particular al problemei rent de pe spoj?
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int n,m, Max;
struct order{ int s,f,c;};
struct vect {int final, cost;};
int A[10005],q;
order a[10005];
inline int cmp(order a, order b)
{
if (a.f>b.f)
return 0;
return 1;
}
void sorteaza_chestia_asta()
{
sort(a+1,a+1+n,cmp);
}
int cauta_bin_un_indice_bun(int nr, int m)
{
int *p = upper_bound(A+1, A + m+1, nr);
return p-A-1;
}
int main()
{
int i,t,z,ind,costc;
fstream f,g;
f.open("heavymetal.in",ios::in);
g.open("heavymetal.out",ios::out);
//f>>t;
t=1;
while (t--)
{
f>>n;
for (i=1;i<=n;i++)
{
f>>a[i].s;
f>>a[i].f;
a[i].c=a[i].f-a[i].s;
}
sorteaza_chestia_asta();
A[1]=a[1].f;
Max=a[1].c;
for (i=2;i<=n;i++)
{
A[i]=a[i].f;
ind=cauta_bin_un_indice_bun(a[i].s,i);
a[i].c+=a[ind].c;
Max=max(Max,a[i].c);
a[i].c=Max;
}
g<<a[n].c<<' ';
}
}