Cod sursa(job #2900383)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 10 mai 2022 19:50:09
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_N = 50005;
const int LIMIT = 50000;

int fx[MAX_N], fy[MAX_N];
int n, dx, dy, x, y;

static inline int dist(const int& q, const int& lft, const int& rgt){
    if(lft <= q && q <= rgt) return 0;
    if(q < lft) return lft - q;
    return q - rgt;
}

int solve(const int& sw, int frq[]){
    int st = 0, dr = sw-1, crt = 0;

    int trecut = 0, viitor = 0;
    for(int i=dr+1; i<=LIMIT; i++)
        viitor += frq[i], crt += frq[i] * dist(i, st, dr);

    int sol = crt;
    while(dr < LIMIT){
        st++, dr++;

        trecut += frq[st-1], crt += trecut;
        crt -= viitor, viitor -= frq[dr];

        sol = min(sol, crt);
    }
    return sol;
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>dx>>dy;
    dx++, dy++;
    for(int i=1; i<=n; i++){
        fin>>x>>y;
        fx[x]++;
        fy[y]++;
    }

    fout<<solve(dx, fx) + solve(dy, fy);
    return 0;
}