Pagini recente » Cod sursa (job #1925755) | Cod sursa (job #1190848) | Cod sursa (job #1440614) | Cod sursa (job #587773) | Cod sursa (job #432984)
Cod sursa(job #432984)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
class Gutuie{
public:
unsigned int greutate, nivel;
};
bool comp1(Gutuie a, Gutuie b){
if( a.nivel < b.nivel )
return false;
else
if( a.nivel == b.nivel ){
if( a.greutate > b.greutate )
return true;
else
return false;
}
else
return true;
}
bool comp2(unsigned int a, unsigned int b){
return a > b;
}
inline unsigned int nivel( unsigned int a, unsigned int u, unsigned int hmax ){
if( a % u <= hmax % u )
return a / u;
else
return a / u + 1;
}
int main(){
unsigned int n, u, hmax;
FILE * fin = fopen( "gutui.in", "r" );
FILE * fout = fopen( "gutui.out", "w" );
fscanf( fin, "%u %u %u", &n, &hmax, &u );
unsigned int i, x, y;
vector<Gutuie> v(n);
for(i = 0; i < n; i++){
fscanf(fin, "%u %u", &x, &y);
v[i].greutate = y;
v[i].nivel = nivel(x, u, hmax);
}
sort( v.begin(), v.end(), comp1 );
unsigned int nivmax = nivel(hmax, u, hmax), niv = v[0].nivel, nr = 0;
vector<unsigned int> greutate;
for(i = 0; i < n; i++){
if( v[i].nivel == niv ){
if( nr < nivmax - niv + 1 ){
nr ++;
greutate.push_back( v[i].greutate );
}
}
else{
inplace_merge( greutate.begin(), greutate.end() - nr, greutate.end(), comp2 );
greutate.resize( nivmax - niv + 1 );
niv = v[i].nivel;
nr = 0;
i --;
}
}
inplace_merge( greutate.begin(), greutate.end() - nr, greutate.end(), comp2 );
greutate.resize( nivmax - niv + 1 );
unsigned int gmax = 0;
for(i = 0; i < greutate.size(); i++)
gmax += greutate[i];
fprintf(fout, "%u\n", gmax);
fclose(fout);
fclose(fin);
return 0;
}