Cod sursa(job #2661151)

Utilizator adiaioanaAdia R. adiaioana Data 21 octombrie 2020 14:41:49
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#define NMAX 50100
using namespace std;
ifstream cin("tribute.in");
ofstream cout("tribute.out");

long long Ox[NMAX][2], Oy[NMAX][2];
int N,ymx,xmx, DX, DY;
inline void scan();
inline void sumpart();
int main()
{
    scan();
    sumpart();

    long long sum=0, Xmin=10e10, Ymin=10e10;
    for(int cx=1; cx+DX<=xmx+1; ++cx)
    {
        sum=cx*Ox[cx-1][1]-Ox[cx-1][0];
        sum+=(-cx-1)*(Ox[xmx][1]-Ox[cx+DX][1])+(Ox[xmx][0]-Ox[cx+DX][0]);
        if(Xmin>sum)
            Xmin=min(Xmin,sum);
    }
    for(int cy=1; cy<=ymx+1; ++cy)
    {
        sum=cy*Oy[cy-1][1]-Oy[cy-1][0];
        sum+=(-cy-1)*(Oy[ymx][1]-Oy[cy+DY][1])+(Oy[ymx][0]-Oy[cy+DY][0]);
        Ymin=min(Ymin,sum);
    }
    sum=Xmin+Ymin;
    cout<<sum<<'\n';
    return 0;
}

inline void scan()
{
    int x,y;
    cin>>N>>DX>>DY;
    for(int i=1; i<=N; ++i)
    {
        cin>>x>>y;
        x++; y++;
        Ox[x][0]+=x;
        Ox[x][1]++;
        Oy[y][0]+=y;
        Oy[y][1]++;
        xmx=max(xmx, x);
        ymx=max(ymx, y);
    }
}

inline void sumpart()
{
    for(int i=1; i<=max(ymx,xmx)+2+max(DX,DY); ++i)
        for(int j=0; j<2; ++j)
            Ox[i][j]+=Ox[i-1][j],
            Oy[i][j]+=Oy[i-1][j];
}
/*
2 2 2 2 17 17
2 2 2 2 5 5
1 5 5 9 14 14
1 3 3 4 5 5
*/
/*for(int j=0; j<2; ++j, cout<<'\n')
        for(int i=1; i<=max(ymx,xmx)+2+max(DX,DY); ++i)
            cout<<Ox[i][j]<<' ';

    for(int j=0; j<2; ++j, cout<<'\n')
        for(int i=1; i<=max(ymx,xmx)+2+max(DX,DY); ++i)
            cout<<Oy[i][j]<<' ';*/