Cod sursa(job #2627423)

Utilizator StanCatalinStanCatalin StanCatalin Data 10 iunie 2020 17:17:31
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("tribute.in");
ofstream out("tribute.out");

const int dim = 50005;

int dx,dy,n,cate_x[dim],cate_y[dim],dp_x[dim],dp_y[dim],sume_x[dim],sume_y[dim];
pair<int,int> a[dim];

int Dist(int x_punct, int y_punct,int x_start,int y_start)
{
    int distanta = 0;
    if (y_start >= y_punct)
    {
        distanta += (y_start - y_punct);
        if (x_start  >= x_punct)
        {
            distanta += (x_start - x_punct);
        }
        else
        {
            if (x_start + dx >= x_punct)
            {
                distanta += (x_start + dx - x_punct);
            }
        }
    }

    if (y_start + dy <= y_punct)
    {
        distanta += (y_punct - y_start - dy);
        if (x_start >= x_punct)
        {
            distanta += (x_start - x_punct);
        }
        else
        {
            if (x_start + dx >= x_punct)
            {
                distanta += (x_start + dx - x_punct);
            }
        }
    }

    if (y_start <= y_punct && y_punct <= y_start + dy)
    {
        if (x_start >= x_punct)
        {
            distanta += (x_start - x_punct);
        }
        else
        {
            if (x_start + dx >= x_punct)
            {
                distanta += (x_start + dx - x_punct);
            }
        }
    }
    return distanta;
}

int main()
{
    in >> n >> dx >> dy;
    for (int i=1; i<=n; i++)
    {
        in >> a[i].first >> a[i].second;
        cate_x[a[i].first]++;
        cate_y[a[i].second]++;
    }
    sume_x[0] = cate_x[0];
    sume_y[0] = cate_y[0];
    for (int i=1; i<dim; i++)
    {
        sume_x[i] = cate_x[i] + sume_x[i-1];
        sume_y[i] = cate_y[i] + sume_y[i-1];
    }
    for (int i=dx+1; i<dim; i++) dp_x[0] += cate_x[i]*(i - dx);
    for (int i=dy+1; i<dim; i++) dp_y[0] += cate_y[i]*(i - dy);
    int mini_x = dp_x[0];
    int mini_y = dp_y[0];
    for (int i=1; i<5; i++)
    {
        dp_x[i] = dp_x[i-1] - (sume_x[dim-1] - sume_x[min(i+dx-1, dim-1)]) + (sume_x[max(0, i - 1)]);
        ///cout << dp_x[i] << " ";
        mini_x = min(mini_x, dp_x[i]);
    }
    ///cout << "\n";
    for (int i=1; i<5; i++)
    {
        dp_y[i] = dp_y[i-1] - (sume_y[dim-1] - sume_y[min(i+dy-1 ,dim-1)]) + (sume_y[max(0, i-1)]);
        //cout << dp_y[i] << " ";
        mini_y = min(mini_y, dp_y[i]);
    }
    out << mini_x + mini_y;
    return 0;
}