Cod sursa(job #3233676)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 4 iunie 2024 13:58:47
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <iostream>
#include <fstream>
#include <vector>
//#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, dx, dy; fin >> n >> dx >> dy;
    vector <ll> x, y;

    for(int i = 0; i < n; i++){
        int l, r; fin >> l >> r;
        x.push_back(l);
        y.push_back(r);
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    ll sp[x.size() + 1];
    sp[0] = 0;
    for(int i = 0; i < n; i++){
        sp[i + 1] = sp[i] + x[i];
    }

    /*cout << "x : ";
    for(int i = 0; i < n; i++) cout << x[i] << " ";
    cout << '\n';

    cout << "sp : ";
    for(int i = 0; i <= n; i++) cout << sp[i] << " ";
    cout << '\n';*/

    int i1 = 0, i2 = 0;
    ll l = 0, r = dx;
    ll mini = -1;

    for(;r <= x.back(); l++, r++){
        while(i2 < x.size() && x[i2] <= r) i2++;
        while(i1 < x.size() && x[i1] < l) i1++; 

        //cout << "l = " << l << " r = " << r << " i1 = " << i1 << " i2 = " << i2;

        ll sum = 0;
        sum += l * i1 - sp[i1];
        sum += (sp[n] - sp[i2]) - r * (n - i2);

        //cout << " sum = " << sum << '\n';
        //cout << "  -- > l = " << l * i1 - sp[i1] << '\n';
        //cout << "  -- > r = " << (sp[n] - sp[i2]) - r * (n - i2) << '\n';

        if(mini == -1 || sum < mini) mini = sum;
    }

    //cout << "minim pe OX : " << mini << '\n';

    sp[0] = 0;
    for(int i = 0; i < n; i++){
        sp[i + 1] = sp[i] + y[i];
    }

    /*cout << "y : ";
    for(int i = 0; i < n; i++) cout << y[i] << " ";
    cout << '\n';

    cout << "sp : ";
    for(int i = 0; i <= n; i++) cout << sp[i] << " ";
    cout << '\n';*/

    i1 = 0, i2 = 0;
    l = 0, r = dy;
    ll mini1 = -1;

    for(;r <= y.back(); l++, r++){
        while(i2 < y.size() && y[i2] <= r) i2++;
        while(i1 < y.size() && y[i1] < l) i1++; 

        //cout << "l = " << l << " r = " << r << " i1 = " << i1 << " i2 = " << i2;

        ll sum = 0;
        sum += l * i1 - sp[i1];
        sum += (sp[n] - sp[i2]) - r * (n - i2);

        //cout << " sum = " << sum << '\n';
        //cout << "  -- > l = " << l * i1 - sp[i1] << '\n';
        //cout << "  -- > r = " << (sp[n] - sp[i2]) - r * (n - i2) << '\n';

        if(mini1 == -1 || sum < mini1) mini1 = sum;
    }

    //cout << "mini m pe oy = " << mini1 << '\n';

    fout << mini + mini1 << '\n';

    return 0;
}