Cod sursa(job #1452114)

Utilizator PopaVladVlad Popa PopaVlad Data 19 iunie 2015 21:14:19
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
// Created by PhantomCracker. Copyright(c) PhantomCracker

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("tribute.in");
ofstream fout ("tribute.out");
int N, dx, dy, x, y, sol, minx, maxx, miny, maxy, OX[50010], OY[50010];
 
int Det_Dist_Min(int V[], int d, int st, int dr)
{
    int sum = 0;
    for (int i=st+d; i<=dr; i++)
    {
        sum += (i - (st + d)) * V[i];
    }
    int minim = sum;
    for (int i=st+1; i<=dr; i++)
    {
        V[i] += V[i-1];
    }
    for (int i=st+1; i<=dr-d; i++)
    {
        sum += V[i-1];
        sum -= N;
        sum += V[i+d-1];
        if (sum < minim) minim = sum;
    }
    return minim;
}
 
int main()
{
    fin >> N >> dx >> dy;
    for (int i=1; i<=N; i++)
    {
        fin >> x >> y;
        if (x < minx) minx = x;
        if (x > maxx) maxx = x;
        if (y < miny) miny = y;
        if (y > maxy) maxy = y;
        OX[x]++;
        OY[y]++;
    }
     
    sol += Det_Dist_Min(OX, dx, minx, maxx);
    sol += Det_Dist_Min(OY, dy, miny, maxy);
     
    fout << sol << '\n';
    fout.close();
    return 0;
}