Pagini recente » Cod sursa (job #3255253) | Cod sursa (job #935593) | Cod sursa (job #2151918) | Cod sursa (job #794951) | Cod sursa (job #429636)
Cod sursa(job #429636)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
class Gutuie{
public:
unsigned int greutate, inaltime;
};
bool comp(Gutuie a, Gutuie b){
return a.inaltime > b.inaltime;
}
inline unsigned int max( unsigned int a, unsigned int b ){
return a < b ? b : a;
}
int main(){
unsigned int n, hmax, u;
FILE * fin = fopen( "gutui.in", "r" );
FILE * fout = fopen( "gutui.out", "w" );
fscanf( fin, "%u %u %u", &n, &hmax, &u );
unsigned int i, j;
vector<Gutuie> v(n);
for(i = 0; i < n; i++)
fscanf(fin, "%u %u", &v[i].inaltime, &v[i].greutate);
sort( v.begin(), v.end() , comp);
//printf("%d\n", nivmax);
/*for(i = 0; i < n; i++)
printf("%d %d\n", v[i].inaltime, v[i].greutate);*/
vector<unsigned int> max1(n + 1);
vector<unsigned int> max2(n + 1);
unsigned int k = 1;
if( v[0].inaltime <= hmax ) {
max1[1] = v[0].greutate;
k = 1;
}
for(i = 2; i <= n; i++){
for(j = 0; j <= k; j++){
if( v[i - 1].inaltime + j * u <= hmax )
max2[j + 1] = max( max1[j] + v[i - 1].greutate, max1[j + 1] );
else
break;
}
if( max2[k] )
k++;
for(j = 0; j <= k; j++)
max1[j] = max2[j];
}
unsigned int maxim = 0;
for(i = 0; i < k; i++)
if( max1[i] > maxim )
maxim = max1[i];
fprintf(fout, "%d\n", maxim);
fclose(fout);
fclose(fin);
return 0;
}