Pagini recente » Cod sursa (job #2045978) | Cod sursa (job #233760) | Cod sursa (job #1168825) | Cod sursa (job #2024769) | Cod sursa (job #442690)
Cod sursa(job #442690)
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define INF 100000
using namespace std;
void sortare(int x[],int y[],int n)
{
int temp,tempor,i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if (x[i]<x[j]){
temp=x[i];
x[i]=x[j];
x[j]=temp;
tempor=y[i];
y[i]=y[j];
y[j]=tempor;
}
}
int main()
{
int N, H, U; // nr. gutui, inaltime maxima, cu cat se ridica
int nn;
int u[100], g[100];
int i, j, min, poz, maxim = -INF;
int *Number, *Sum, *renunt;
FILE *f1,*f2;
f1=fopen("gutui.in","r");
f2=fopen("gutui.out","w");
fscanf(f1,"%d %d %d",&N,&H,&U);
for(i=0;i<N;i++)
fscanf(f1,"%d %d",&u[i],&g[i]);
// sortat descrescator dupa inaltime
sortare(u,g,N);
renunt = (int *)malloc(N * sizeof(int));
Sum = (int *)malloc(N * sizeof(int));
Number = (int*)malloc(N * sizeof(int));
Sum[0] = g[0];
Number[0] = 1;
for(i = 1; i < N; i++)
{
// cout<<height[i] + NrGutui[i - 1] * u<<" ";
if((u[i] + Number[i - 1] * U) <= H)
{
Sum[i] = Sum[i - 1] + g[i];
Number[i] = Number[i - 1] + 1;
}
else
{
// Nu poti sa culegi gutuia i
Number[i] = Number[i - 1];
Sum[i] = Sum[i - 1];
min = INF;
poz = 0;
// Incerci sa renunti la una culeasa, astfel incat daca ai renunta la ea
// si ai culege gutuia i, ai avea un profit mai mare
for(j = 0; j < i; j++)
if((renunt[j] == 0) && (min > g[j]))
{
min = g[j];
poz = j;
}
if(min < g[i])
{
renunt[poz] = 1;
Sum[i] = Sum[i - 1] -g[poz] + g[i];
}
else
renunt[i] = 1;
}
//cout<<Sol[i]<<" "<<NrGutui[i]<<"\n" ;
}
fprintf(f2,"%d",Sum[N-1]);
fclose(f1);
fclose(f2);
return 0;
}