Cod sursa(job #32954)

Utilizator cos_minBondane Cosmin cos_min Data 18 martie 2007 19:07:58
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <vector>
#include <iterator>
#include <set>
using namespace std;

#define in "lupu.in"
#define out "lupu.out"

int val[100001], timp[100001];

struct Functor {
       bool operator () (int i, int j)
       {
            return val[i] > val[j];
       }
};

vector< vector<int> > ts;
multiset<int, Functor> s;
int n, d, t;

int main()
{
    int tmax=0, x;
    FILE *fin = fopen(in,"r");
    
    char linie[101]; // nu o sa fie niciodata mai mare de 30 :P
    
    freopen(out,"w",stdout);
    
    fscanf(fin,"%d%d%d",&n,&t,&d);
    fscanf(fin,"\n");
    
    for ( int i = n; i > 0; --i )
    {
      //  scanf("%d%d",&x,&val[i]);
        int x=0;
        int p=0;
        int j=0;
        fgets(linie,31,fin);
        
        while ( linie[j] != ' ' )
        {
              x *= 10;
              x += (int)linie[j]-48;
              j++;
        }
        j++;
        while ( linie[j] != '\n' )
        {
              p *= 10;
              p += (int)linie[j]-48;
              j++;
        }
        
        val[i] = p;
        if ( x > t ) timp[i] = -1;
        else         
        {
             timp[i] = (t-x)/d;  
        }
        
        if ( tmax < (t-x)/d ) tmax = (t-x)/d;
    }
    
    ts.resize(tmax+1);
    
    for ( int i = n; i > 0; --i )
    {
        if ( timp[i] != -1 ) ts[timp[i]].push_back(i);
    }
    
    long long maxim=0;
    
    for ( int j = tmax; j >= 0; --j ) 
    {
        if ( ts[j].size() != 0 )
        { 
             for ( int i = ts[j].size()-1; i >= 0; --i )
             {
                 s.insert(ts[j][i]);
             }
        }
        maxim += val[*s.begin()];
        s.erase(s.begin());
    }
    
    printf("%lld",maxim);
}