Cod sursa(job #1082256)

Utilizator teoionescuIonescu Teodor teoionescu Data 14 ianuarie 2014 13:02:41
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<queue>
#include<algorithm>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
ifstream in("tribute.in");
ofstream out("tribute.out");
const int Nmax = 50;
int X[Nmax+5],Y[Nmax+5],dx,dy;
int N;
queue<int> q;
int Get(int V[],int d){
    int Min=(1<<30);
    sort(V+1,V+N+1);
    int j=1,prev=0,next=N;
    int dprev=0,dnext=V[0];
    for(int i=0;i<=Nmax+2*d;i++){
        while(!q.empty() && q.front()<i-d){
            prev++;
            q.pop();
        }
        if(i>0){
            dprev+=prev;
            dnext-=next;
        }
        while(i==V[j]){
            next--;
            q.push(V[j]);
            j++;
        }
        Min=min(Min,dprev+dnext);
    }
    return Min;
}
int main(){
    in>>N>>dx>>dy;
    for(int i=1;i<=N;i++){
        in>>X[i]>>Y[i];
        X[0]+=X[i];
        Y[0]+=Y[i];
    }
    out<<Get(X,dx)+Get(Y,dy);
    return 0;
}