Cod sursa(job #1814281)

Utilizator Coroian_DavidCoroian David Coroian_David Data 23 noiembrie 2016 20:18:15
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 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);
}

void solve()
{
    int i, j;

    int first = 0, last;

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

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

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

    mnx = sx[0];

    for(i = 1; i <= 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] < mnx)
            mnx = sx[i];
    }

    first = 1;

    for(i = 1; i <= n; i ++)
    {
        if(y[i] > ly)
        {
            if(sy[0] == 0)
                last = i;

            sy[0] += (y[i] - ly);
        }
    }

    mny = sy[0];

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

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

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

        if(sy[i] < mny)
            mny = sy[i];
    }
}

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

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

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}