Cod sursa(job #2539495)

Utilizator stef2003Bud Stefan stef2003 Data 5 februarie 2020 21:51:28
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct ura{
  int in, sf;
};

ura v[100001];
int sol[100000];

bool cmp(ura a, ura b) {
  if(a.sf<b.sf)
    return true;
  if(a.sf==b.sf && a.in>b.in)
    return true;
  return false;
}

int main() {
  FILE *fin, *fout;
  int n, i, j;
  fin=fopen("heavymetal.in","r");
  fout=fopen("heavymetal.out","w");
  fscanf(fin, "%d",&n);
  for(i=1;i<=n;i++)
    fscanf(fin, "%d%d",&v[i].in,&v[i].sf);
  sort(v+1,v+n+1,cmp);
  j=1;
  for(i=1;i<=v[n].sf;i++) {
    sol[i]=sol[i-1];
    while(v[j].sf==i) {
      if(sol[v[j].in]+v[j].sf-v[j].in>sol[i])
        sol[i]=sol[v[j].in]+v[j].sf-v[j].in;
      j++;
    }
  }
  fprintf(fout, "%d",sol[v[n].sf]);
  fclose( fin );
  fclose( fout );
  return 0;
}