Cod sursa(job #1419869)

Utilizator Liviu98Dinca Liviu Liviu98 Data 16 aprilie 2015 23:47:38
Problema Tribute Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define NMax 50002
#define INF 999999999
using namespace std;
int N,Vx[NMax],Vy[NMax],Sol[NMax+1],rez,x,y;

int solve(int V[NMax],int lungime)
{
    int i1=0,j1=0,rez1;
    sort(V+1,V+N+1);
    for(int i=1;i<=N;i++)
        Sol[i]=Sol[i-1]+V[i];
    for(int i=0;i+lungime<=NMax;i++)
    {
        while(i1<N && V[i1+1]<i)
        {
            ++i1;
        }
        while(j1<N && V[j1+1]<i+lungime)
        {
            ++j1;
        }
        rez1=min(rez1,i*i1-Sol[i1]+(Sol[N]-Sol[j1])-(i+lungime)*(N-j1));
    }
    return rez1;
}

int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%d%d%d",&N,&x,&y);
    for(int i=1;i<=N;i++)
    {
        scanf("%d%d",&Vx[i],&Vy[i]);
    }
    rez=solve(Vx,x)+solve(Vy,y);
    printf("%d",rez);
}