Cod sursa(job #2163248)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 12 martie 2018 17:29:27
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>

using namespace std;

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

const int MAX = 50001;

int f1[MAX], f2[MAX];

int gaslat(int f[], int l) {
    int s[MAX], st[MAX];
    s[0] = f[0];
    for (int i = 1; i < MAX; ++i) {
        s[i] = s[i - 1] + f[i];
    }
    st[0] = 0;
//    cout << 0 << " ";
    for (int i = 1; i < MAX; ++i) {
        st[i] = st[i - 1] + s[i - 1];
//        cout << st[i] << " ";
    }
    s[MAX - 1] = 0;
    for (int i = MAX - 2; i >= 0; --i) {
        s[i] = s[i + 1] + f[i];
    }
    int mind(st[MAX - l - 1]), dist(0);
//    cout << "\n" << dist << " ";
    for (int i = MAX - 2; i >= l; --i) {
        dist += s[i + 1];
//        cout << dist << " ";
        mind = min(mind, dist + st[i - l]);
    }
//    cout << "\n";
    return mind;
}

int main()
{
    int n, l1, l2, a;
    cin >> n >> l1 >> l2;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        ++f1[a];
        cin >> a;
        ++f2[a];
    }
    cout << gaslat(f1, l1) + gaslat(f2, l2) << "\n";
    return 0;
}