Pagini recente » Istoria paginii runda/oni_2009_baraj | Cod sursa (job #743001) | Cod sursa (job #1734104) | Cod sursa (job #1911669) | Cod sursa (job #436470)
Cod sursa(job #436470)
#include <stdio.h>
#define interschimb(a, b) a ^= b; b ^= a; a ^= b
#define N 100000
struct {
int h, w;
} gutui[N];
int n, hmax, u, taken[N];
void read() {
int i;
scanf("%d %d %d", &n, &hmax, &u);
for ( i = 0; i < n; i++ ) {
taken[i] = 0;
scanf("%d %d", &gutui[i].h, &gutui[i].w);
}
}
void sort() {
int i, flag = 0;
while(!flag) {
flag = 1;
for ( i = 0; i < n-1; i++ )
if ( gutui[i].h < gutui[i+1].h ) {
interschimb(gutui[i].w, gutui[i+1].w);
interschimb(gutui[i].h, gutui[i+1].h);
flag = 0;
}
}
}
void print() {
int i;
for ( i = 0; i < n; i++ )
printf("%d %d %d %d\n", gutui[i].h, gutui[i].w, (hmax - gutui[i].h)/u, taken[i]);
}
int getNextStep( int currStep ) {
int i = 0;
for ( i = 0; i < n; i++ )
if ( !taken[i] && (hmax - gutui[i].h)/u >= currStep )
return (hmax - gutui[i].h)/u;
return -1;
}
int selectQuince (int currStep, int nextStep) {
int max = -1, i, quince = -1;
for ( i = 0; i < n; i++ ) {
if (!taken[i] && (hmax - gutui[i].h)/u == nextStep && max < gutui[i].w) {
max = gutui[i].w;
quince = i;
}
}
return quince;
}
int main() {
int currStep = 0, nextStep = 0, nextQuince = 0, gmax = 0;
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
read();
sort();
for ( currStep = 0; currStep < n && nextQuince >= 0 && nextStep >= 0; currStep++ ) {
nextStep = getNextStep(currStep);
nextQuince = selectQuince(currStep, nextStep);
if(nextQuince >= 0) {
taken[nextQuince] = 1;
gmax += gutui[nextQuince].w;
printf("%d %d %d\n", currStep, nextStep, gutui[nextQuince].w);
}
/* Debug stuff
else {
printf("%d\tno queen!\n", currStep);
}
*/
}
// print();
printf("%d \n", gmax);
return 0;
}