Cod sursa(job #1360419)

Utilizator maribMarilena Bescuca marib Data 25 februarie 2015 14:40:25
Problema Tribute Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#define DIM 50000
#define minim(a, b) ((a<b)?a:b)
using namespace std;

int min_x, min_y, c1, c2, res, n, dim1, dim2;

int ox[DIM+1], oy[DIM+1], sumx[DIM+1], sumy[DIM+1];

int main()
{
    ifstream in("tribute.in");
    ofstream out("tribute.out");
    min_x=0x3f3f3f; min_y=min_x;
    in>>n>>dim1>>dim2;
    for(int i=1; i<=n; ++i)
    {
        in>>c1>>c2;
        ox[c1]++;
        oy[c2]++;
    }
    for(int i=1; i<=DIM; ++i)
    {
        sumx[i]=sumx[i-1]+ox[i]*i;
        sumy[i]=sumy[i-1]+oy[i]*i;
        ox[i]=ox[i]+ox[i-1];
        oy[i]=oy[i-1]+oy[i];
    }
    for(int niv=dim1; niv<=DIM; ++niv)
    {
        //cele de mai sus
        res=sumx[DIM]-sumx[niv]-niv*(ox[DIM]-ox[niv]);
        //cele de mai jos
        if(niv>dim1)
        {
            res+=(ox[niv-dim1-1]*(niv-dim1));
            res-=(sumx[niv-dim1-1]);
        }
        min_x=minim(min_x, res);
    }
    for(int niv=dim2; niv<=DIM; ++niv)
    {
        //cele din dreapta
        res=sumy[DIM]-sumy[niv]-niv*(oy[DIM]-oy[niv]);
        //cele din stanga
        if(niv>dim2)
        {
            res+=(oy[niv-dim2-1]*(niv-dim2));
            res-=(sumy[niv-dim2-1]);
        }
        min_y=minim(min_y, res);
    }
    out<<(min_x+min_y)<<"\n";
    in.close();
    out.close();
    return 0;
}