Cod sursa(job #2627857)

Utilizator AokijiAlex M Aokiji Data 12 iunie 2020 21:05:17
Problema Tribute Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <cstring>
#define m 50000
#include <climits>

using namespace std;

ifstream f("tribute.in");
ofstream g("tribute.out");

int i,j,n,dx,dy,mx,my;
long long v[50001],stx[100001],drx[100001],frx[50001],x,y,fry[50001],sty[100001],dry[100001];

int main()
{   f>>n>>dx>>dy;
    for(i=1;i<=n;i++){
        f>>x>>y;
        frx[x]++;
        fry[y]++;
    }
    //x
    v[0]=frx[0];
    for(i=1;i<=m;i++)
    {
        stx[i]=stx[i-1]+v[i-1];
        v[i]=v[i-1]+frx[i];
    }
    memset(v,0,sizeof(v));
    for(i=m;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<=m;i++)
    {
        sty[i]=sty[i-1]+v[i-1];
        v[i]=v[i-1]+fry[i];
    }
    memset(v,0,sizeof(v));
    for(i=m;i>=0;i--)
    {
        dry[i]=dry[i+1]+v[i+1];
        v[i]=v[i+1]+fry[i];
    }
    long long mini=LLONG_MAX;
    long long S=0;
    for(i=0;i<=m-dx;i++)
        if(mini>stx[i]+drx[i+dx])
            mini=stx[i]+drx[i+dx];
    S+=mini;
    for(i=0;i<=m-dy;i++)
        if(mini>sty[i]+dry[i+dy])
            mini=sty[i]+dry[i+dy];
    S+=mini;
    g<<S;
    return 0;
}