Pagini recente » Cod sursa (job #27594) | Cod sursa (job #2727973) | Cod sursa (job #106456) | Cod sursa (job #36674) | Cod sursa (job #2729711)
#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;
}