Cod sursa(job #447119)

Utilizator vladiiIonescu Vlad vladii Data 27 aprilie 2010 19:08:50
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
using namespace std;
#define maxn 50010
#define inf 999999999

int N, DX, DY;
int S[maxn];
int sol, solx, soly;
int x[maxn], y[maxn];

int main() {
    FILE *f1=fopen("tribute.in", "r"), *f2=fopen("tribute.out", "w");
    int i, j, p, q, k;
    int pos, start, end;
    int sum, xmax = 0, ymax = 0;
    fscanf(f1, "%d %d %d\n", &N, &DX, &DY);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d\n", &p, &q);
         x[p]++; y[q]++;
         xmax=max(xmax, p);
         ymax=max(ymax, q);
    }
    solx = soly = inf;
    S[0] = x[0];
    for(i=1; i<=xmax; i++) {
         S[i] = S[i-1] + x[i];
    }
    int last;
    last = 0;
    for(i=DX+1; i<=xmax; i++) {
         last+=((i - DX) * x[i]);
    }
    solx = last;
    for(i=1; i<=xmax - DX; i++) {
         last += (S[i-1] - S[xmax] + S[i + DX -1]);
         solx = min(solx, last);
    }
    memset(S, 0, sizeof(S));
    S[0] = y[0];
    for(i=1; i<=ymax; i++) {
         S[i] = S[i-1] + y[i];
    }
    last = 0;
    for(i=DY+1; i<=ymax; i++) {
         last+=((i - DY) * y[i]);
    }
    soly = last;
    for(i=1; i<=ymax - DY; i++) {
         last += (S[i-1] - S[ymax] + S[i + DY -1]);
         soly = min(soly, last);
    }
    sol = solx + soly;
    
    fprintf(f2, "%d\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}