Cod sursa(job #2337751)

Utilizator vladadAndries Vlad Andrei vladad Data 6 februarie 2019 18:12:25
Problema Trapez Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 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,fry[50005],frx[50005];
long long v[50005],stx[50005],drx[50005],x,y,sty[50005],dry[50005];
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];
    }
    for(i=m; i>=0; i--)
    {
        drx[i]=drx[i+1]+v[i+1];
        v[i]=v[i+1]+frx[i];
    }
    //y
    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];
    }
    for(i=m; i>=0; i--)
    {
        dry[i]=dry[i+1]+v[i+1];
        v[i]=v[i+1]+fry[i];
    }
    long long mini1=LLONG_MAX;
    long long mini2=LLONG_MAX;
    for(i=0; i<=m-dx; i++)
        if(mini1>stx[i]+drx[i+dx])
            mini1=stx[i]+drx[i+dx];
    for(i=0; i<=m-dy; i++)
        if(mini2>sty[i]+dry[i+dy])
            mini2=sty[i]+dry[i+dy];
    g<<mini1+mini2;
    return 0;
}