Pagini recente » Cod sursa (job #940822) | Cod sursa (job #1221450) | Cod sursa (job #2767075) | Cod sursa (job #3257276) | Cod sursa (job #437236)
Cod sursa(job #437236)
#include<stdlib.h>
#include<stdio.h>
typedef struct{
int * height;
int * weight;
int max;
int el;
int flag;
}pom;
void minweight(int s[], int x,int n,int sign){
int i = 0,j,l;
if (sign == 1) j = 1;
else j = 0;
//int * c = (int*)malloc(n*sizeof(int));
int c[n];
while (j<n){
if ((s[j]< x) && (s[j]!=0)) c[i] = s[j];
else
break;
j++;
i++;
}
c[i] = x;
i++;
for (;j<n;j++){
c[i] = s[j];
i++;
}
for (l = 0; l<n; l++)
s[l] = c[l];
}
int main(int argc, char * argv[]){
int n,u,h,hi,gi;
int i,j,x,ind,s = 0;
int * sum;
FILE * fis = fopen("gutui2.in","r");
if (fis == NULL) printf("Couldn't open file\n");
FILE * out = fopen("gutui.out","w");
fscanf(fis,"%d",&n);
fscanf(fis,"%d",&h);
fscanf(fis,"%d",&u);
pom * v = (pom*)malloc((h/u)*sizeof(pom));
for (i = 0; i<n; i++){
v[i].max = 0;
v[i].el = 0;
v[i].flag = 0;
v[i].height = (int*) malloc((i+1)*sizeof(int));
v[i].weight = (int*) malloc((i+1)*sizeof(int));
}
ind = 0;
for (i = 0; i<n; i++){
fscanf(fis,"%d %d",&hi,&gi);
if ((h - hi) % u == 0) ind = (h - hi)/u - 1;
else ind = (h - hi)/u;
v[ind].flag = 1;
if (v[ind].max <= gi){
v[ind].max = gi;
if (ind + 1 > v[ind].el){
//v[i].weight = (int*)realloc(v[i].weight,(v[ind].el+1)*sizeof(int));
//v[i].height = (int*)realloc(v[i].height,(v[ind].el+1)*sizeof(int));
for (j = v[ind].el; j>0; j--){
v[ind].weight[j] = v[ind].weight[j-1];
v[ind].height[j] = v[ind].height[j-1];
}
v[ind].el++;
}else{
if (ind + 1 == v[ind].el){
for (j = v[ind].el-1; j>0; j--){
v[ind].weight[j] = v[ind].weight[j-1];
v[ind].height[j] = v[ind].height[j-1];
}
}
}
v[ind].weight[0] = gi;
v[ind].height[0] = hi;
}
}
/*
printf("\n");
for (i = 0; i<h/u; i++){
if (v[i].flag == 1) {
printf("pom:%d %d",i,v[i].flag);
for (j = 0; j<v[i].el; j++)
printf("%d %d,",v[i].weight[j],v[i].height[j]);
}
printf("\n");
}
*/
x = 0;
sum = (int*)calloc(n,sizeof(int));
for (i = 0; i<h/u ; i++){
if (v[i].flag == 1){
for (j = 0; j<v[i].el; j++){
if (v[i].height[j] + u*(x+1) <= h+u){
s = s + v[i].weight[j];
x++;
minweight(sum,v[i].weight[j],n,0);
}
else{
if (v[j].weight[j] > sum[0]){
s = s - sum[0];
s = s + v[i].weight[j];
minweight(sum,v[i].weight[j],n,1);
}
}
}
}
}
//printf("%d",s);
fprintf(out,"%d",s);
fclose(out);
fclose(fis);
return 0;
}