Cod sursa(job #1322182)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 19 ianuarie 2015 20:40:13
Problema Lupul Urias si Rau Scor 92
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.88 kb
#include <iostream>
#include <cstdio>       
#include <algorithm>    
#include <queue>        
using namespace std;
FILE *f,*g;
int n,x,l,i,j,mx,crt;
unsigned long long sol;
struct o {int d,w,nr;}v[100001];
bool cmp (o i,o j) { return (i.nr < j.nr); }
int main()
{
    f = fopen("lupu.in","r");
    g = fopen("lupu.out","w");
    fscanf(f,"%d %d %d", &n, &x, &l);
    for(i = 0 ; i < n ; i ++)
	{
        fscanf(f,"%d %d",&v[j].d,&v[j].w);
		v[j].nr=(int)(x-v[i].d)/l;
        if(v[i].d<=x)++j;
    }
	n=j;
    sort (v, v + n, cmp);
    mx = v[n - 1].nr;
    crt = n - 1;
    priority_queue < int > q;
    for(i=mx;i>=0;i--)
	{
        while(v[crt].nr==i) 
		{
            q.push(v[crt].w);
            crt --;
        }
        if(!q.empty()) 
		{
            sol += q.top();
            q.pop();
        }
    }

    fprintf(g,"%llu",sol);
    return 0;
}