Cod sursa(job #3154925)

Utilizator SSKMFSS KMF SSKMF Data 6 octombrie 2023 20:11:35
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
using namespace std;

ifstream cin ("tribute.in");
ofstream cout ("tribute.out");

long long suma[2][50003];
int aparitii[2][50001];

int main ()
{
    int numar_locatii , lungime[2];
    cin >> numar_locatii >> lungime[0] >> lungime[1];

    for (int indice = 1 , abscisa , ordonata ; indice <= numar_locatii ; indice++)
        { cin >> abscisa >> ordonata; aparitii[0][abscisa]++; aparitii[1][ordonata]++; }

    long long suma_minima = 0;
    lungime[0]++; lungime[1]++;
    for (int indice = 0 ; indice <= 1 ; indice++)
    {
        int total = aparitii[indice][0];
        suma[0][0] = aparitii[indice][0];
        for (int coordonata = 1 ; coordonata <= 50000 ; coordonata++)
            suma[0][coordonata] = suma[0][coordonata - 1] + (total += aparitii[indice][coordonata]);

        total = 0;
        for (int coordonata = 50000 ; coordonata >= 0 ; coordonata--)
            suma[1][coordonata] = suma[1][coordonata + 1] + (total += aparitii[indice][coordonata]);

        long long minim = suma[1][lungime[indice]];
        for (int inceput = 1 ; inceput + lungime[indice] <= 50001 ; inceput++)
            minim = min(minim , suma[0][inceput - 1] + suma[1][inceput + lungime[indice]]);
            
        suma_minima += minim;
    }

    cout << suma_minima;
    cout.close(); cin.close();
    return 0;
}