Cod sursa(job #2298046)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 7 decembrie 2018 00:16:41
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <limits.h>
#define x first
#define y second
#define dim 50002
using namespace std;
 int fr[dim], st[dim], dr[dim], pst[dim], pdr[dim], minim[3];
int n, dx, dy, t, i, stanga;
/// in pst si pdr tinem numarul de puncte pana la indicele curent
///int st si dr distantele totale de la puncte la indice
pair<int, int> p[dim];
int main () {
    ifstream fin ("tribute.in");
    ofstream fout("tribute.out");
    fin>>n>>dx>>dy;

    for (i=1;i<=n;i++)
        fin>>p[i].x>>p[i].y;

    for (t = 1; t <= 2; t++) {

        for (i=0;i<=50000;i++)
            fr[i] = 0;
        for (i=1;i<=n;i++)
            if (t == 1)
                fr[ p[i].x ]++;
            else
                fr[ p[i].y ]++;
      /// prima parcurgere din stanga
        st[0]=0; pst[0]=fr[0];
        for (i=1;i<=50000;i++) {
            st[i] = st[i-1] + pst[i-1];
            pst[i] = pst[i-1] + fr[i];
        }
        /// a doua parcurgere din dreapta
        dr[50000] = 0;
        pdr[50000] = fr[50000];
        for (i=49999; i>=0; i--) {
            dr[i] = dr[i+1] + pdr[i+1];
            pdr[i] = pdr[i+1] + fr[i];
        }

        minim[t] = INT_MAX;
        for (stanga = 0; stanga + dx <= 50000; stanga++)
            minim[t] =min(minim[t],st[stanga] + dr[stanga+dx]) ;
 /// se patreaza minimul distantelor pentru fiecare posibiliatete
        swap(dx,dy);
        /// se inverseaza axele pentru a rezolva si pentru oY
    }

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

    return 0;
}