Cod sursa(job #2540509)

Utilizator eusebiu_alexandruMorar Eusebiu eusebiu_alexandru Data 7 februarie 2020 11:53:25
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb

#include<fstream>
#include<algorithm>
#define nmax 100007

using namespace std;
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
struct ana
{
    int x,y;
}v[nmax];
bool cmp(ana a,ana b)
{
    if(a.y!=b.y)
         return a.y<b.y;
    return a.x>b.x;
}
int sol[nmax],n,i,j;
int main()
{
f>>n;
for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;
 sort(v+1,v+n+1,cmp);
 sol[1]=v[1].y-v[1].x;
 for(i=2;i<=n;i++)
 {
      sol[i]=sol[i-1]; /// nu il pun
      j=i-1;
      while(j && v[j].y>v[i].x)
            j--;
      sol[i]=max(sol[i],sol[j]+v[i].y-v[i].x);
 }
 g<<sol[n];
}