Pagini recente » Cod sursa (job #3208800) | Cod sursa (job #3265429) | Cod sursa (job #2811837) | Cod sursa (job #9189) | Cod sursa (job #2783650)
#include <bits/stdc++.h>
#define DIM 50000
using namespace std;
ifstream fin ("tribute.in");
ofstream fout ("tribute.out");
int n, dx, dy;
int st[DIM+5], dr[DIM+5], x[DIM+5], y[DIM+5];
int l, m, r, p, u;
int solve(int v[], int len){
sort(v+1, v+n+1);
st[1]=0;
for(int i=2; i<=n; i++)
st[i] = st[i-1] + (v[i]-v[i-1]);
dr[n]=0;
for(int i=n-1; i>=1; i--)
dr[i] = dr[i+1] + (v[i+1]-v[i]);
for(int i=1; i<=n; i++) cout<<v[i]<<" "; cout<<"\n";
int sol=(1 << 30), sum;
for(int i=0; i+len-1 <= v[n]; i++){
p=u=0;
l=1; r=n;
while(l <= r){
m=(r-l)/2+l;
if(v[m] < i){
l=m+1;
p=m;
}else
r=m-1;
}
l=1; r=n;
while(l <= r){
m=(r-l)/2+l;
if(v[m] <= i+len-1)
l=m+1;
else{
r=m-1;
u=m;
}
}
sum=0;
if(p != 0)
sum += (i-v[p])*p + st[p];
if(u != 0)
sum += (v[u] - (i+len-1)) * (n-u+1) + dr[u];
cout<<i<<" "<<p<<" "<<u<<" "<<sum<<"\n";
sol=min(sol, sum);
}
return sol;
}
int main (){
fin>>n>>dx>>dy;
for(int i=1; i<=n; i++)
fin>>x[i]>>y[i];
fout<<solve(y, dy);// + solve(y, dy);
return 0;
}