Cod sursa(job #1519578)

Utilizator ancabdBadiu Anca ancabd Data 7 noiembrie 2015 15:50:15
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>

using namespace std;

ifstream fin ("tribute.in" );
ofstream fout("tribute.out");

#define DIM 150010

int n, m, i, j, k, id, jd, x, y, d[5][DIM], v[DIM], w[DIM];
int max1, max2, nr1, maxtot, nr2;
int minim1, minim2;

void SetUp()
{
    fin >> n >> id >> jd;
    for(i = 1; i <= n; i ++){
        fin >> x >> y;
        v[x] += 1; w[y] += 1;
        if(max1 < x) max1 = x;
        if(max2 < y) max2 = y;
    }
    nr1 = 0; nr2 = 0; maxtot = max1;
    if(maxtot < max2) maxtot = max2;
    for(i = 0; i <= maxtot * 2; i ++){
        if(i <= max1 * 2 && i >= 1) d[1][i] = d[1][i-1] + nr1;
        if(i <= max1 * 2 && i <= 0) d[1][i] = d[0][i-i] + nr1;
        if(i <= max2 * 2 && i >= 1) d[3][i] = d[3][i-1] + nr2;
        if(i <= max2 * 2 && i <= 0) d[3][i] = d[0][i-i] + nr2;
        if(v[i] >= 1) nr1 += v[i];
        if(w[i] >= 1) nr2 += w[i];
    }
    nr1 = 0; nr2 = 0;
    for(i = maxtot * 2; i >= 0; i --){
        if(i <= max1 * 2) d[2][i] = d[2][i+1] + nr1;
        if(i <= max2 * 2) d[4][i] = d[4][i+1] + nr2;
        if(v[i] >= 1) nr1 += v[i];
        if(w[i] >= 1) nr2 += w[i];
    }
    return;
}

void Baleiere_1()
{
    minim1 = d[2][id];
    for(i = 1; i <= max1; i ++)
        if(minim1 > d[1][i] + d[2][id+i])
            minim1 = d[1][i] + d[2][id+i];
    return;
}

void Baleiere_2()
{
    minim2 = d[4][jd];
    for(i = 1; i <= max2; i ++)
        if(minim2 > d[3][i] + d[4][jd+i])
            minim2 = d[3][i] + d[4][jd+i];
    return;
}

int main()
{
    SetUp();
    Baleiere_1();
    Baleiere_2();
    fout << minim1 + minim2;
    return 0;
}