Cod sursa(job #1702842)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 15 mai 2016 16:52:37
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <algorithm>
#define F 3000000
using namespace std;
int N,X,L,d,M=0,p=1,Z=0,H[100001]={},P;
long long int S=0;
char f[F]={};
struct A{int t,V;}v[100001];
bool c(A a,A b){return a.t>b.t;}
void r(int &n){
n=0;
while(f[P]<'0'||f[P]>'9')
P++;
while(f[P]>='0'&&f[P]<='9')
n=n*10+f[P++]-'0';}
void R(){
fread(f, 1, F, stdin);
r(N);r(X);r(L);
for(int i=1;i<=N;i++){
r(d);r(v[i].V);
v[i].t=(X-d)/L+1;
if(v[i].t>M)M=v[i].t;}
sort(v+1,v+N+1,c);}
void G(int e,int &u){
H[++u]=e;
int i=u;
while(i>1&&H[i/2]<H[i]){
int t=H[i/2];
H[i/2]=H[i];
H[i]=t;
i/=2;}}
void K(int p,int u){
int y=2*p,z=2*p+1,b;
if(y<=u&&H[y]>H[p])b=y;
else b=p;
if(z<=u&&H[z]>H[b])b=z;
if(p!=b){
int t=H[b];
H[b]=H[p];
H[p]=t;
K(b,u);}}
void E(int p,int &u){
int t=H[p];
H[p]=H[u];
H[u--]=t;
K(p,u);}
int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
R();
for(int i=M;i>0;i--){
while(v[p].t==i&&p<=N){
G(v[p].V,Z);
p++;}
if(Z>1){
S+=H[1];
E(1,Z);}
else if(Z==1){
S+=H[1];
Z--;}}
printf("%lld",S);
return 0;}