Cod sursa(job #500689)

Utilizator andra23Laura Draghici andra23 Data 12 noiembrie 2010 20:47:28
Problema Tribute Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<fstream>
#include<iostream>
#define maxn 50000

using namespace std;

ofstream g("tribute.out");

int solve(int a[], int c, int l) {
    int s1 = 0;
    int nr1 = 0, nr2 = 0;
    int s = 2000000000;
    int i;
    
    for (i = 0; i <= maxn && a[i] == 0; i++);
    int start = i + l;
    
    for (i = start+1; i <= c; i++){
        int d = i - start;
        s1 = s1 + a[i]*d;
        nr2 = nr2 + a[i];
    }
    
    for (i = start+1; i <= c; i++){
        nr1 = nr1 + a[i-l-1];
        s1 = s1 + nr1;
        s1 = s1 - nr2;
        nr2 = nr2 - a[i];
        if (s1 < s)
            s = s1;
    }
    
    return s;
}

int main(){
    ifstream f("tribute.in");
    
    int n, dx, dy;
    f >> n >> dx >> dy;
    int i, j, k, xmax = 0, ymax = 0, a, b;
    int x[maxn+5], y[maxn+5];
    for (i = 1; i <= n; i++){
        f >> a >> b;
        x[a]++;
        y[b]++;
        if (a > xmax)
            xmax = a;
        if (b > ymax)
            ymax = b;    
    }
    
    int result = solve(x, xmax, dx) + solve(y, ymax, dy);
    
    g << result << '\n';
    
    return 0;    
}