Cod sursa(job #440082)

Utilizator encyEnciu Bogdan ency Data 11 aprilie 2010 21:48:00
Problema Gutui Scor 70
Compilator cpp Status done
Runda teme_upb Marime 1.76 kb
#include <stdio.h>
#include <stdlib.h>
int sort(const void *x, const void *y) {
  return (*(int*)y - *(int*)x);
}
void sorta2(unsigned long int a[][2],unsigned long int n){
qsort(a,n,sizeof(unsigned long int[2]),sort);
}
unsigned long int minim (unsigned long int a[][2], int n,unsigned long int u){
    unsigned long int m=1000000000,j=-1;
    for(int i=0;i<n;i++)
        if(a[i][0]<m&&a[i][1]==0) {
            m=a[i][0];
            j=i;
        }
    if (u>m)
        a[j][1]=1;
    return m;
}
unsigned long int gutui(unsigned long int c[][2],unsigned long int n,unsigned long int h,unsigned long int u){
    unsigned long int i,k=0,m=0,z;
    unsigned long int a[n][2];
    unsigned long int r=0;
    if(u>=h) {
        for(i=0;i<n;i++)
            if(m<c[i][1]&&c[i][0]<=h)
                m=c[i][1];
        return m;
         } 
    sorta2(c,n);
    for(i=0;i<n;i++)
        if(k<=h-c[i][0])  {
            m=m+c[i][1];
            a[r][0]=c[i][1];
            a[r][1]=0;
            r++;
            k=k+u;
         }
             else  {
                z=minim(a,r,c[i][1]);
                if(c[i][1]>z) {
                m=m-z;            
                m=m+c[i][1];
                a[r][0]=c[i][1];
                a[r][1]=0;
                r++;               
                 } 
              }                
                 
    return m;
}
int main(){
     unsigned long int c[100000][2];
     unsigned long int i,n,h,gr,j,u;
         freopen("gutui.in", "r", stdin);
         freopen("gutui.out", "w", stdout);
         scanf("%ld",&n);
     scanf("%ld",&h);
     scanf("%ld",&u); 
    for (i=0;i<n;i++) {
                scanf("%ld",&c[i][0]);
            scanf("%ld",&c[i][1]);
            c[i][2]=0;
    }
    gr=gutui(c,n,h,u);
    printf("%ld\n",gr);
    return 0;
}