Cod sursa(job #2335516)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 4 februarie 2019 11:12:15
Problema Tribute Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("tribute.in");
ofstream g("tribute.out");
int i,j,n,dx,dy,minx,miny,maxx,maxy,v[50001],stx[100001],drx[100001],frx[50001],x,y,fry[50001],sty[100001],dry[100001];
int main()
{   f>>n>>dx>>dy;
    maxx=maxy=0;
    minx=miny=50001;
    for(i=1;i<=n;i++){
        f>>x>>y;
        frx[x]++;
        fry[y]++;
        minx=min(minx,x);
        miny=min(miny,y);
        maxx=max(maxx,x);
        maxy=max(maxy,y);
    }
    //x
    v[0]=frx[0];
    for(i=1;i<=50000;i++){
        stx[i]=stx[i-1]+v[i-1];
        v[i]=v[i-1]+frx[i];
    }
    memset(v,0,sizeof(v));
    v[50000]=frx[50000];
    for(i=49999;i>=0;i--){
        drx[i]=drx[i+1]+v[i+1];
        v[i]=v[i+1]+frx[i];
    }
    //y
    memset(v,0,sizeof(v));
    v[0]=fry[0];
    for(i=1;i<=50000;i++){
        sty[i]=sty[i-1]+v[i-1];
        v[i]=v[i-1]+fry[i];
    }
    memset(v,0,sizeof(v));
    v[50000]=fry[50000]=0;
    for(i=49999;i>=0;i--){
        dry[i]=dry[i+1]+v[i+1];
        v[i]=v[i+1]+fry[i];
    }
    int mini=50001;
    int S=0;
    for(i=minx;i<=maxx;i++)
        if(mini>stx[i]+drx[i+dx])
            mini=stx[i]+drx[i+dx];
    S+=mini;
    for(i=miny;i<=maxy;i++)
        if(mini>sty[i]+dry[i+dy])
            mini=sty[i]+dry[i+dy];
    S+=mini;
    g<<S;
    return 0;
}