Cod sursa(job #2729711)

Utilizator mariusn01Marius Nicoli mariusn01 Data 25 martie 2021 10:07:44
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#define x first
#define y second
#define DIM 50002
using namespace std;

int f[DIM], S[DIM], D[DIM], PS[DIM], PD[DIM], minim[3];
int n, dx, dy, t, i, st;
///pair<int, int> p[DIM];
int X[DIM];
int Y[DIM];
int main () {
    ifstream fin ("tribute.in");
    ofstream fout("tribute.out");
    fin>>n>>dx>>dy;

    for (i=1;i<=n;i++)
        fin>>X[i]>>Y[i];

    for (t = 1; t <= 2; t++) { /// cand t=1 se face calculul pentru x iar cand t=2, cu acelasi cod fac calculul pentru y
        for (i=0;i<=50000;i++)
            f[i] = 0;
        for (i=1;i<=n;i++)
            if (t == 1)
                f[ X[i] ]++;
            else
                f[ Y[i] ]++;

        S[0] = 0;
        /**
        PS[i] = cate puncte sunt in stanga pozitiei i, inclusiv pozitia i
        S[i] = suma distantelor tuturor punctelor din stanga pozitiei i
        la capatul din stanga al unui segment care incepe la pozitia i


        **/
        PS[0] = f[0];
        for (i=1;i<=50000;i++) {
            S[i] = S[i-1] + PS[i-1];
            PS[i] = PS[i-1] + f[i];
        }
        /**
        In D[i] voi obtine, cu un procedeu similar celui de sus
        suma distantelor la capatul din dreapta al segmentului (capat fixat in pozitia i)
        de la toate punctele din dreapta pozitiei i
        **/
        D[50000] = 0;
        PD[50000] = f[50000];
        for (i=49999; i>=0; i--) {
            D[i] = D[i+1] + PD[i+1];
            PD[i] = PD[i+1] + f[i];
        }

        /// imi imaginez segmentul ca incepand de la pozitia st di terminandu-se
        /// la pozitia st+dx, deci fixat in acest loc suma distantelor
        /// este S[st] + D[st+dx]
        minim[t] = 2000000000;
        for (st = 0; st + dx <= 50000; st++)
            if (minim[t] > S[st] + D[st+dx])
                minim[t] = S[st] + D[st+dx];

        dx = dy;
    }

    fout<<minim[1] + minim[2];

    return 0;
}