Cod sursa(job #1814306)

Utilizator Coroian_DavidCoroian David Coroian_David Data 23 noiembrie 2016 20:33:01
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>

#include <algorithm>

#include <climits>

using namespace std;

FILE *f, *g;

int n;

long long lx, ly;

long long mnx, mny;

long long x[50001], y[50001];

long long sx[50001], sy[50001];

void readFile()
{
    f = fopen("tribute.in", "r");

    int i;

    fscanf(f, "%d%lld%lld", &n, &lx, &ly);

    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%lld%lld", &x[i], &y[i]);
    }

    fclose(f);
}

long long mn(long long x[], long long sx[], long long lx)
{
    int first = 0, last = 0, i;
    long long mn = LONG_LONG_MAX;

    sort(x + 1, x + n + 1);

    for(i = 1; i <= n; i ++)
    {
        if(x[i] > lx)
        {
            if(sx[0] == 0)
                last = i;

            sx[0] += (x[i] - lx);
        }
    }

    mn = sx[0];

    for(i = 1; i <= x[n] - lx; i ++)
    {
        while(last <= n && x[last] < i + lx)
            last ++;

        while(first < n && x[first] < i)
            first ++;

        sx[i] = sx[i - 1] - ((n - last + 1)) + (first - 1);

       // printf("%d\n", last);

        if(sx[i] < mn)
            mn = sx[i];
    }

    return mn;
}

void solve()
{
    mnx = mn(x, sx, lx);
    mny = mn(y, sy, ly);
}

void printFile()
{
    g = fopen("tribute.out", "w");

    fprintf(g, "%lld\n", mnx + mny);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}