Pagini recente » Cod sursa (job #1547329) | Cod sursa (job #835470) | Cod sursa (job #2241280) | Cod sursa (job #854759) | Cod sursa (job #439611)
Cod sursa(job #439611)
#include <stdio.h>
//#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <numeric>
FILE* fs;
FILE* fd;
int N, max_height, height_inc,i,j,x,increase=0,rest,min,k, minmin,kk,kkk,kkkk,maxh,r;
long long int max_weight=0;
typedef struct {
int height;
int weight;
int getIt;
} gutuie;
gutuie tree[100001];
gutuie newtree[100001];
int compare (const void * a, const void * b)
{
if( ( (*(gutuie*)a).height - (*(gutuie*)b).height ) == 0 )
return ( (*(gutuie*)a).weight - (*(gutuie*)b).weight );
else return ( (*(gutuie*)a).height - (*(gutuie*)b).height );
}
int comp (const void * a, const void * b)
{
return(*(int*)a - *(int*)b);
}
using namespace std;
int main(){
fs = fopen("lupu.in","r");
fd = fopen("lupu.out","w");
if (fs==NULL) {
printf("Eroare");
exit (1);
}
if (fd==NULL) {
printf("Eroare");
exit (1);
}
vector<int> coll;
make_heap (coll.begin(), coll.end());
maxh=0;
fscanf(fs,"%i",&N);
fscanf(fs,"%i",&max_height);
fscanf(fs,"%i",&height_inc);
rest = max_height%height_inc;
max_height=max_height/height_inc;
for(i=0;i<N;i++){
fscanf(fs,"%i",&x);
if(x%height_inc>rest)
tree[i].height = x / height_inc + 1;
else
tree[i].height = x / height_inc;
fscanf(fs,"%i",&x);
tree[i].weight = x;
tree[i].getIt=0;
if(maxh<tree[i].height &&tree[i].height<=max_height) maxh=tree[i].height;
}
kk=max_height - maxh;
qsort(tree,N,sizeof(gutuie),compare);
kkk=0; kkkk=0;
for(i=N-1;i>=0;i--){
if(max_height - tree[i].height == kk){
//printf("salut %i %i %i\n", tree[i].height, tree[i].weight,kk);
newtree[kkkk]=tree[i];
kkk++; kkkk++;
if(kkk>kk) { kk++; kkk=0; }
}
else
if(max_height - tree[i].height > kk){
//printf("salut2 %i %i\n", tree[i].height, tree[i].weight);
newtree[kkkk]=tree[i];
kk=max_height- tree[i].height;
kkk=1;
kkkk++;
}
}
for(i=0;i<kkkk;i++){
if((newtree[i].height+increase)<=max_height){
increase++;
max_weight = max_weight + newtree[i].weight;
coll.push_back ((0-newtree[i].weight));
push_heap (coll.begin(), coll.end());
}
else
if((0-newtree[i].weight) < coll.front()){
max_weight = max_weight + newtree[i].weight;
max_weight = max_weight + coll.front();
pop_heap(coll.begin(), coll.end());
coll.pop_back();
coll.push_back ((0-newtree[i].weight));
push_heap (coll.begin(), coll.end());
}
}
fprintf(fd,"%lli",max_weight);
fclose(fs);
fclose(fd);
}