Cod sursa(job #1024636)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 8 noiembrie 2013 21:29:28
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
using namespace std;

int n, dx, dy, apx[50002], apy[50002], costs[50002], costd[50002], i, x, y, min1, min2, nr;

int main()
{
    ifstream f("tribute.in");
    ofstream g("tribute.out");
    f>>n;
    f>>dx;f>>dy;
    dx++;dy++;
    for(i=1;i<=n;i++)
    {
        f>>x;f>>y;
        apx[x]++;
        apy[y]++;
    }
    nr=0;
    costs[0]=0;
    for(i=1;i<=50000;i++)
    {
        costs[i]=costs[i-1]+nr+apx[i-1];
        nr+=apx[i-1];
    }
    nr=0;
    costd[50000]=0;
    for(i=49999;i>=0;i--)
    {
        costd[i]=costd[i+1]+nr+apx[i+1];
        nr+=apx[i+1];
    }
    min1=1000000000;
    for(i=0;i<=50000-dx+1;i++)
    {
        if(costs[i]+costd[i+dx-1]<min1)
            min1=costs[i]+costd[i+dx-1];
    }
    nr=0;
    costs[0]=0;
    for(i=1;i<=50000;i++)
    {
        costs[i]=costs[i-1]+nr+apy[i-1];
        nr+=apy[i-1];
    }
    nr=0;
    costd[50000]=0;
    for(i=49999;i>=0;i--)
    {
        costd[i]=costd[i+1]+nr+apy[i+1];
        nr+=apy[i+1];
    }
    min2=1000000000;
    for(i=0;i<=50000-dy+1;i++)
    {
        if(costs[i]+costd[i+dy-1]<min2)
            min2=costs[i]+costd[i+dy-1];
    }
    g<<min1+min2<<"\n";
    f.close();g.close();
    return 0;
}