Cod sursa(job #3322994)

Utilizator petric_mariaPetric Maria petric_maria Data 16 noiembrie 2025 15:16:08
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("tribute.in");
ofstream g("tribute.out");

int n, dx, dy;
int ans_oriz = INT_MAX, ans_vert = INT_MAX;

struct date{
    int x, y;
} a[50005];

bool vrf1 (date i, date j) {
    return i.x <= j.x;
}

bool vrf2 (date i, date j) {
    return i.y <= j.y;
}

void orizontala() {
    int sum_ant = 0, sum_post = 0, points_ant = 0, points_post = 0;
    for (int i=1; i<=n; ++i) {
        if (a[i].x > dx) {
            ++points_post;
            sum_post += a[i].x;
        }
    }

    for (int i=0; i+dx<=a[n].x; ++i) {
        if (a[points_ant+1].x <= i) {
            points_ant++;
            sum_ant += a[points_ant].x;
        }
        if (a[n-points_post+1].x <= i) {
            points_post--;
            sum_post -= a[points_post].x;
        }
        int dist;
        dist = points_ant * i - sum_ant + sum_post - points_post * (i+dx);
        ans_oriz = min (ans_oriz, dist);
        //cout << i << ' ' << ans_oriz << endl;
    }

}


void verticala () {
    int sum_ant = 0, sum_post = 0, points_ant = 0, points_post = 0;
    for (int i=1; i<=n; ++i) {
        if (a[i].y > dy) {
            ++points_post;
            sum_post += a[i].y;
        }
    }

    for (int i=0; i+dy<=a[n].y; ++i) {
        if (a[points_ant+1].y <= i) {
            points_ant++;
            sum_ant += a[points_ant].y;
        }
        if (a[n-points_post+1].y <= i) {
            points_post--;
            sum_post -= a[points_post].y;
        }
        int dist;
        dist = points_ant * i - sum_ant + sum_post - points_post * (i+dy);
        ans_vert = min (ans_vert, dist);
        //cout << i << ' ' << ans_vert << endl;
    }
}

int main()
{
    f >> n >> dx >> dy;
    for (int i=1; i<=n; ++i)
        f >> a[i].x >> a[i].y;

    sort (a+1, a+n+1, vrf1);
    orizontala();

    sort (a+1, a+n+1, vrf2);
    verticala();

    g << ans_oriz + ans_vert;
    return 0;
}