Cod sursa(job #71957)
#include <assert.h>
#include <stdio.h>
#define printf(...) /*six feet under's not deep enough*/;
enum { maxsize = 50003, inf = 0x3F3F3F3F };
int horiz_size, vert_size;
int col[maxsize], row[maxsize];
int vert_before[maxsize],
vert_after[maxsize];
int horiz_before[maxsize],
horiz_after[maxsize];
int ans;
void calc()
/*
* Takes O(maxsize) time no matter the input.
*/
{
int count, cost, i, tmp,
best_vert, best_horiz;
//vert_before
count = 0;
cost = 0;
for(i = 0; i < maxsize - vert_size; i++)
{
cost += count; //all previous extended by one
count += col[i]; //free items on current col
vert_before[i] = cost;
}
//vert_after
count = 0;
cost = 0;
for(i = maxsize - 1; i >= vert_size; i--)
{
cost += count;
count += col[i];
vert_after[i - vert_size] = cost;
}
//vert answer
best_vert = inf;
for(i = 0; i < maxsize - vert_size; i++)
{
tmp = vert_before[i] + vert_after[i];
printf("i %d vert before %d after %d sum %d\n",
i, vert_before[i], vert_after[i], tmp);
if(tmp < best_vert)
best_vert = tmp;
}
printf("vert_answer %d\n", best_vert);
//horiz_before
count = 0;
cost = 0;
for(i = 0; i < maxsize - horiz_size; i++)
{
cost += count;
count += row[i];
horiz_before[i] = cost;
}
//horiz_after
count = 0;
cost = 0;
for(i = maxsize - 1; i >= horiz_size; i--)
{
cost += count;
count += row[i];
horiz_after[i - horiz_size] = cost;
}
//horiz answer
best_horiz = inf;
for(i = 0; i < maxsize - horiz_size; i++)
{
tmp = horiz_before[i] + horiz_after[i];
printf("i %d horiz before %d after %d sum %d\n",
i, horiz_before[i], horiz_after[i], tmp);
if(tmp < best_horiz)
best_horiz = tmp;
}
printf("horiz_answer %d\n", best_horiz);
ans = best_vert + best_horiz;
printf("sum %d\n", ans);
}
int main()
{
int count, a, b, i;
FILE *f = fopen("tribute.in", "r");
if(!f) return 1;
fscanf(f, "%d%d%d", &count, &horiz_size, &vert_size);
for(i = 0; i < count; i++)
{
fscanf(f, "%d%d", &a, &b);
row[a]++;
col[b]++;
}
fclose(f);
f = fopen("tribute.out", "w");
if(!f) return 1;
calc();
fprintf(f, "%d\n", ans);
fclose(f);
return 0;
}