Cod sursa(job #22520)

Utilizator cos_minBondane Cosmin cos_min Data 26 februarie 2007 19:33:57
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <stdio.h>
#include <vector>
#include <iterator>
#include <set>
using namespace std;

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

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

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

int main()
{
    int tmax=0, x;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d%d",&n,&t,&d);
    
    val.resize(n+1);
    timp.resize(n+1);
    
    for ( int i = 1; i <= n; i++ )
    {
        scanf("%d%d",&x,&val[i]);
        
        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 = 1; i <= n; i++ )
    {
        ts[timp[i]].push_back(i);
    }
    
    long long maxim=0;
    
    for ( int i = 0; i < ts[tmax].size(); i++ )
    {
        s.insert(ts[tmax][i]);
    }
    
    maxim = val[*s.begin()];
    s.erase(s.begin());
    
    
    for ( int j = tmax-1; j >= 0; j-- ) 
    {
        if ( ts[j].size() != 0 )
        { 
             for ( int i = 0; i < ts[j].size(); i++ )
             {
                 s.insert(ts[j][i]);
             }
        }
        
        maxim += val[*s.begin()];
        s.erase(s.begin());
    }
    
    /* for ( int j = 0; j <= tmax; j++ ) 
     {
         for ( int i = 0; i <= 1; i++ )
         {
             printf("%d ", a[i][j] );
         }
         printf("\n");
         
     }*/
    
    //for ( int i = 1; i <= n; i++ ) printf("%d ", );
    
    printf("%lld",maxim);
}