Cod sursa(job #2147542)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 28 februarie 2018 20:14:40
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<algorithm>

using namespace std;

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

int N,L1,L2,X[50003],Y[50003],MinX,MinY,PozY,PozX;

int main()
{
    fin>>N>>L1>>L2;
    for(int i=1; i<=N; i++)
    {
        int C,D;
        fin>>C>>D;
        X[C]++;
        Y[D]++;
    }
    int Before=0,After=0,Inside=0,DistAft=0,DistBef=0;
    for(int i=0; i<=50000; i++)
        if(X[i]>0 && i<=L1)
            Inside+=X[i];
        else
        {
            After+=X[i];
            DistAft=DistAft+X[i]*(i-L1);
        }
        MinX=DistAft;
    for(int i=L1+1;i<=50000;i++)
    {
        DistAft=DistAft-After;
        if(X[i]!=0)
        {
            Inside=Inside+X[i];
            After=After-X[i];
        }
        if(X[i-L1-1]!=0)
        {
            Inside=Inside-X[i-L1-1];
            Before=Before+X[i-L1-1];
        }
        DistBef=DistBef+Before;
        if(DistBef+DistAft<MinX)
            {
                MinX=DistBef+DistAft;
                PozX=i;
            }
    }
    Before=0,After=0,Inside=0,DistAft=0,DistBef=0;
    for(int i=0; i<=50000; i++)
        if(Y[i]>0 && i<=L2)
            Inside+=Y[i];
        else
        {
            After+=Y[i];
            DistAft=DistAft+Y[i]*(i-L2);
        }
        MinY=DistAft;
    for(int i=L2+1;i<=50000;i++)
    {
        DistAft=DistAft-After;
        if(Y[i]!=0)
        {
            Inside=Inside+Y[i];
            After=After-Y[i];
        }
        if(Y[i-L2-1]!=0)
        {
            Inside=Inside-Y[i-L2-1];
            Before=Before+Y[i-L2-1];
        }
        DistBef=DistBef+Before;
        if(DistBef+DistAft<MinY)
            {
                MinY=DistBef+DistAft;
                PozY=i;
            }
    }
    fout<<MinX+MinY<<'\n';
    return 0;
}