Cod sursa(job #2627426)

Utilizator StanCatalinStanCatalin StanCatalin Data 10 iunie 2020 17:21:37
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 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 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];
    int mi_pana_in_5x = dp_x[0];
    int mi_pana_in_5y = dp_y[0];
    for (int i=1; i<dim; 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]);
        if (i < 5) mi_pana_in_5x = min(mi_pana_in_5x, dp_x[i]);
    }
    ///cout << "\n";
    for (int i=1; i<dim; 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]);
        if (i < 5) mi_pana_in_5y = min(mi_pana_in_5y, dp_y[i]);
    }
    out << min(mini_x + mini_y, mi_pana_in_5x + mi_pana_in_5y);
    return 0;
}