Cod sursa(job #2809469)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 27 noiembrie 2021 02:23:08
Problema Lupul Urias si Rau Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

#define MAXN 100000

struct in{
  int dist, lana;
};
in v[MAXN];

struct aux{
  int dist, nrop, lana;
  bool operator < (const aux &other) const{
    if(nrop > other.nrop){
      return true;
    }else if(nrop == other.nrop){
      if(lana < other.lana){
        return true;
      }else{
        return false;
      }
    }else{
      return false;
    }
  }
};
priority_queue <aux>ord;

bool cmp(struct in a, struct in b){
  return (a.lana > b.lana);
}

int main()
{
    FILE *fin, *fout;
    int n, x, l, i;
    long long s;
    fin = fopen("lupu.in", "r");
    fscanf(fin, "%d%d%d", &n, &x, &l);
    for(i = 0; i < n; i++){
      fscanf(fin, "%d%d", &v[i].dist, &v[i].lana);
    }
    fclose(fin);
    sort(v, v + n, cmp);
    i = 0;
    while((i < (x / l + 1)) && (i < n)){
      ord.push({v[i].dist, (x - v[i].dist) / l, v[i].lana});
      i++;
    }
    s = 0;
    while((i < n) && (!ord.empty())){
      if(ord.top().dist <= x){
        s += ord.top().lana;
        x -= l;
        ord.pop();
      }else{
        ord.pop();
        ord.push({v[i].dist, (x - v[i].dist) / l, v[i].lana});
        i++;
      }
    }
    while(!ord.empty()){
      if(ord.top().dist <= x){
        s += ord.top().lana;
        x -= l;
      }
      ord.pop();
    }
    fout = fopen("lupu.out", "w");
    fprintf(fout, "%lld", s);
    fclose(fout);
    return 0;
}