Vlada zemlje Bajtovije je odlučila da poboljša infrastrukturu puteva izgradnjom novog autoputa. Autoput ima oblik prave linije, koja je paralelna sa Y osom. Dužina puta može biti proizvoljno velika. Cilj izgradnje novog puta je da on bude dostupan što većem broju građana te zemlje. Poznato je da će žitelji određenog grada koristiti autoput ako najkraće rastojanje od njihovog grada do tog puta nije veće od graničnog rastojanja D.

Ulaz:

U prvom redu datoteke autoput.in se nalazi broj gradova u Bajtoviji, N ≤ 50000 i broj D, koji su razdvojeni razmakom. U narednih N redova sledi opis svakog grada koji čine tri broja razdvojena razmakom. Najpre su upisane koordinate X i Y, a potom sledi broj žitelja tog grada. Svi brojevi u datoteci su prirodni i manji od 100000.

Izlaz:

U prvom i jedinom redu izlazne datoteke autoput.out ispisati maksimalan broj stanovnika Bajtovije koji će koristiti autoput. Garantuje se da taj broj neće preći dve milijarde.

Primer:

5 2
11 9 1000
2 5 2000
7 5 10000
5 8 1000
9 2 5000

16000

Autoput će biti prava X=7, tako da će biti dostupan trećem, četvrtom i petom gradu iz ulaza.

Najpre ćemo sortirati gradove prema X koordinatama. Zatim, krenuvši sa leve na desnu stranu, vodimo računa o intervalu koji je manji ili jednak 2D. Kako novi grad ,,uđe'' u interval, tako trenutnoj sumi dodajemo broj stanovnika grada, a kada grad više nije u intervalu, onda smanjimo sumu za njegov broj stanovnika. U svakom trenutku proveravamo da li trenutna suma prevazilazi maksimalnu sumu.

Pseudokod

SORT-GRADOVI
l = 0 
max = 0
FOR d = 0 to n-1
	WHILE x[d] - x[l] > 2D
		l++
		sum = sum - s[l]
	sum += s[d]
	IF sum > max THEN
		max = sum
RETURN max

Složenost ovog algoritma je O(Nlog(N)). To je složenost sortiranja. Složenost petlje je linearna zbog toga što ukupan broj iteracija kroz WHILE petlju ne može da pređe N.

#include <cstdlib>
#include <fstream>
#include <stdlib.h>

using namespace std;

#define MAX 50005

// x i y su koordinate, a z je broj stanovnika
typedef struct{
        int x, y, z;
} city;


// koristi se za uporedjivanje gradova po x koordinati
// zbog quick sorta
int up(const void *px, const void* py){
    city* a = (city*) px;
    city* b = (city*) py;
    if (a->x < b->x) return -1;
    if (a->x > b->x) return 1;
    return 0;
}

int main(int argc, char *argv[])
{
    
    ifstream in("autoput.in");
    ofstream out("autoput.out");
    int x, y, z, n, d, i;
    int max = 0, sum = 0, l, r;
    city gradovi[MAX];
    
    in >> n >> d;
    for (i = 0; i < n; i++){
        city c;
        in >> c.x >> c.y >> c.z;
        gradovi[i] = c;
    }
    qsort(gradovi, n, sizeof(city), up);
    
    l = 0; max = gradovi[0].z; sum = gradovi[0].z;
    for (r = 1; r < n; r++){
        while (gradovi[r].x-gradovi[l].x>2*d)
              sum -= gradovi[l++].z;
        sum += gradovi[r].z;
        max >?= sum;
    }
    out << max << endl;
    in.close();
    out.close();
    return EXIT_SUCCESS;
}