Cod sursa(job #2547275)

Utilizator ptudortudor P ptudor Data 15 februarie 2020 10:50:23
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");
int n,x,l;
pair<int,int> oi[100005],t[100005];
int main()
{int i,j;
   in >> n >> x >> l;
   for (i = 1; i <= n; i++){
      in >> oi[i].first >> oi[i].second; ///distanta si cantitatea
      t[i] = { (x - oi[i].first) / l + 1, oi[i].second}; /// numarul de ture si cnt
   }
     // for (i = 1; i <= n; i++) cout << t[i].first << " cnt = " << t[i].second << "\n";

   sort(t + 1 , t + 1 + n);
   priority_queue <int> q;
   int cr,st;
   long long sol = 0;
   for (i = n; i >= 1; i--)
   {
      if (!q.empty())
      {
         cr = t[i + 1].first - t[i].first;
         while(cr--){
            sol += q.top();
            q.pop();
         }
      }

      st = t[i].first;
      while(st == t[i].first)
      {
         q.push(t[i].second);
         st--;
      }
   }
   cr = t[1].first;
   while(cr--){
      sol += q.top();
      q.pop();
   }
   out << sol << "\n";
   out.close();
   in.close();
   return 0;
}
/**
t este timpul dupa care o sa iasa si cantitatea de lana
Le sortam descrescator si facem maximul
*/