Cod sursa(job #2527877)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 20 ianuarie 2020 22:52:56
Problema Tribute Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define Nmax 50005
#define INF 0x3f3f3f3f
#define x first
#define y second

using namespace std;

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

int n, dx, dy;
pair <int, int> v[Nmax];
int frx[Nmax], fry[Nmax];
int prefsumx[Nmax], prefsumy[Nmax];
int pctx, pcty, ansx=INF, ansy=INF;

void solvex()
{
    for (int i = Nmax-5; i >=0; i--)
    {
        prefsumx[i]=prefsumx[i+1]+pctx;
        pctx+=frx[i];
    }

    pctx=0;
    int cntx=0;
    for (int i = 0; i <= Nmax-5; i++)
    {
        cntx+=pctx;
        ansx=min(ansx, cntx+prefsumx[i+dx]);
        pctx+=frx[i];
    }
}

void solvey()
{
    for (int i = Nmax-5; i >=0; i--)
    {
        prefsumy[i]=prefsumy[i+1]+pcty;
        pcty+=fry[i];
    }

    pcty=0;
    int cnty=0;
    for (int i = 0; i <= Nmax-5; i++)
    {
        cnty+=pcty;
        ansy=min(ansy, cnty+prefsumy[i+dy]);
        pcty+=fry[i];
    }
}

int main()
{
    f >> n >> dx >> dy;

    for (int i = 1, x, y; i <= n; i++)
    {
        f >> x >> y;
        frx[x]++;
        fry[y]++;
    }

    solvex();
    solvey();

    g << ansx+ansy << " ";
    return 0;
}