Cod sursa(job #527812)

Utilizator darrenRares Buhai darren Data 1 februarie 2011 12:17:17
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;

int N, D1, D2;
int X[50002], Y[50002];
int Sp1[50002], Sp2[50002];
int Sc1[50002], Sc2[50002];
int Xmin = 1 << 30, Ymin = 1 << 30;

int main()
{
    ifstream fin("tribute.in");
    ofstream fout("tribute.out");

    fin >> N >> D1 >> D2;
    for (int i = 1, px, py; i <= N; ++i)
    {
        fin >> px >> py;
        ++X[px], ++Y[py];
    }
    for (int i = 0; i <= 50000; ++i)
    {
        Sp1[i] = Sp1[i - 1] + X[i];
        Sc1[i] = Sc1[i - 1] + X[i] * i;
        Sp2[i] = Sp2[i - 1] + Y[i];
        Sc2[i] = Sc2[i - 1] + Y[i] * i;
    }

    for (int i = 0; i + D1 <= 50000; ++i)
    {
        int costx1 = Sp1[i - 1] * i - Sc1[i - 1];
        int costx2 = Sc1[50000] - Sc1[i + D1] - (Sp1[50000] - Sp1[i + D1]) * (i + D1);
        Xmin = min(Xmin, costx1 + costx2);
    }

    for (int i = 0; i + D2 <= 50000; ++i)
    {
        int costy1 = Sp2[i - 1] * i - Sc2[i - 1];
        int costy2 = Sc2[50000] - Sc2[i + D2] - (Sp2[50000] - Sp2[i + D2]) * (i + D2);
        Ymin = min(Ymin, costy1 + costy2);
    }

    fout << Xmin + Ymin;

    fin.close();
    fout.close();
}