Cod sursa(job #2561810)

Utilizator andreitabaraandrei2004 andreitabara Data 29 februarie 2020 10:21:02
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct kys {int x,y;};
kys v[10000];
long long n,i,s[100000],j,cmax;
int comp (kys a,kys b)
{
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
int main()
{
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,comp);
   for(i=n;i>=1;i--)
   {
       s[i]=v[i].y-v[i].x;
       for(j=i+1;j<=n;j++)
       {
           if(v[i].y<=v[j].x&&s[j]+(v[i].y-v[i].x)>s[i])
           {
               s[i]=s[j]+(v[i].y-v[i].x);
           }
       }
   }
for(i=1;i<=n;i++)
{
    if(s[i]>cmax)cmax=s[i];
}
out<<cmax;
    return 0;
}