Pagini recente » Cod sursa (job #2428579) | Cod sursa (job #2433908) | Cod sursa (job #3282823) | Cod sursa (job #2768140) | Cod sursa (job #2818460)
/// ALTERNATE SOLUTION
#include <bits/stdc++.h>
using namespace std;
ifstream f("gutui.in");
ofstream g("gutui.out");
const int N = 100010;
int n,H,G;
struct gutuie
{
int greutate,timp;
gutuie()
{
int x,y;
f>>x>>y;
greutate = y;
if(x>H)timp=-1;
else if(x+n*G<=H)timp=N;
else timp=(H-x)/G;
}
};
bool crit(gutuie A,gutuie B)
{
if(A.greutate>B.greutate)
return true;
if(A.greutate<B.greutate)
return false;
return A.timp>=B.timp;
}
vector<gutuie> GU;
set<int> timpi;
int64_t sol;
int main()
{
f>>n>>H>>G;
for(int i=0; i<n; i++)
{
timpi.insert(-i);
gutuie gu;
if(gu.timp==N)
sol+=gu.greutate;
else if(gu.timp>=0)
GU.push_back(gu);
}
sort(GU.begin(),GU.end(),crit);
for(auto it:GU)
{
auto IT=timpi.lower_bound(-it.timp);
if(IT!=timpi.end())
{
sol+=it.greutate;
timpi.erase(IT);
}
}
g<<sol;
return 0;
}
/// PRIMARY SOLUTION
//#include <bits/stdc++.h>
//
//using namespace std;
//ifstream f("gutui.in");
//ofstream g("gutui.out");
//const int N = 100010;
//int n,hMaxim,hInitial,crestere,greutate,gutuiMax,gutuiPuse;
//int64_t sol;
//vector<int> greutati[N];
//priority_queue<int> candidati;
//int main()
//{
// int hMaxim,crestere;
// f>>n>>hMaxim>>crestere;
// for(int i=1; i<=n; i++)
// {
// int hInitial,greutate;
// f>>hInitial>>greutate;
// if(hInitial<=hMaxim)
// {
// gutuiMax=(hMaxim-hInitial)/crestere;
// if(gutuiMax>=n)
// sol+=greutate;
// else
// greutati[gutuiMax].push_back(greutate);
// }
// }
// for(gutuiMax=0; gutuiMax<n; gutuiMax++)
// if(greutati[gutuiMax].size())
// for(auto Greutate:greutati[gutuiMax])
// if(gutuiPuse<=gutuiMax)
// {
// sol+=Greutate;
// candidati.push(-Greutate);
// gutuiPuse++;
// }
// else if(Greutate>-candidati.top())
// {
// sol+=candidati.top();
// sol+=Greutate;
// candidati.pop();
// candidati.push(-Greutate);
// }
// g<<sol;
// return 0;
//}