Pagini recente » Cod sursa (job #438503) | Cod sursa (job #2262528) | Cod sursa (job #1280432) | Cod sursa (job #1407599) | Cod sursa (job #437841)
Cod sursa(job #437841)
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
typedef struct gs{
unsigned int ng;
unsigned int gg;
unsigned int hg;
} gs;
unsigned int h,u;
unsigned int n;
gs *gt;
unsigned int *q /* cate am luat de pe niv. respectiv */;
char * l;
//unsigned int nr_luate = 0;
unsigned int p;
unsigned int gmax = 0;
unsigned int nivmax = 0;
unsigned int nivmin = UINT_MAX;
int compare (const void * a, const void * b)
{
if( ((gs *)b)->gg != ((gs *)a)->gg ){
if ( ((gs *)b)->gg > ((gs *)a)->gg ){
return 1;
}
else{
return -1;
}
}
else{
if( ((gs *)b)->hg > ((gs *)a)->hg ){
return 1;
}
else
if ( ((gs *)b)->hg < ((gs *)a)->hg ){
return -1;
}
else{
return 0;
}
}
}
int get_gmax(){
unsigned int i, j, k, t, y, flag;
for(i=0;i<p;i++){
if(i==n){
break;
}
if(gt[i].hg > h){
p++;
continue;
}
flag = 1;
/*
for(j=gt[i].ng + 1; j<= nivmax;j++){
k = k + nivmax + 1 - j - q[j];
}*/
//y = nivmax + 1 - gt[i].ng - q[gt[i].ng];
for(j=0; j<= gt[i].ng - 1;j++){
//cout<<nivmax + 1 - j << endl;
if( q[j] == 0 && l[gt[j].ng] == 1 ){
flag = 0;
break;
}
}
//cout<<endl<<endl;
/*
TODO:
-nu pot lua elementul curent daca am luat deja alte elemente care se afla "mai jos" ca el,
consumandu-i astfel pozitia
*/
if( ( q[gt[i].ng] > 0 ) && flag ){
q[gt[i].ng]--;
l[gt[i].ng] = 1;
for(j=0; j<= gt[i].ng - 1;j++){
if( q[j] > 0 ){
q[j]--;
}
}
gmax = gmax + gt[i].gg;
}
else{
p++;
}
}
return 0;
}
int read_vec(){
ifstream fin;
unsigned int i, j;
//int nvc;
unsigned int ic;
int f = 1;
int o;
fin.open("gutui.in",ios::in);
fin>>n;
fin>>h;
fin>>u;
o = u - ( h % u ) - 1;
h = h + o;
gt = (gs *)malloc( n * sizeof( gs ));
nivmax = h / u;
ic = h;
for(i=0;i<n;i++){
fin>>gt[i].hg;
fin>>gt[i].gg;
gt[i].hg = gt[i].hg + o;
gt[i].ng = gt[i].hg / u;
if(gt[i].ng < nivmin){
nivmin = gt[i].ng;
}
}
p = nivmax - nivmin + 1;
if(p > n){ //??
p = n;
}
q = (unsigned int *)malloc( (nivmax + 1) * sizeof( unsigned int ));
l = (char *)malloc( (nivmax + 1) * sizeof( char ));
for(i=0;i<=nivmax;i++){
q[i] = nivmax + 1 - i;
l[i] = 0;
}
qsort (gt, n, sizeof(gs), compare);
fin.close();
return 0;
}
int write_sol(){
ofstream fout;
fout.open("gutui.out",ios::out);
fout<<gmax;
fout.close();
return 0;
}
int main(){
read_vec();
get_gmax();
write_sol();
//cin.get();//to_comment
return 0;
}