Cod sursa(job #2508885)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 13 decembrie 2019 11:53:30
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005;
long long ln[N],cl[N];
long long solve(long long n,long long v[],long long r){
  long long sum=0,summin=1<<30;
  for(long long i=1;i<=n;i++){
    sum+=v[i];
  }
  long long st=1,dr=0;
  for(st=1;st<=n;st++){
    sum+=(st-1)*(v[st]-v[st-1]);
    while(dr<=n && v[dr+1]-v[st]+1<=r){
      sum-=(v[dr+1]-v[dr])*(n-dr);
      dr++;
    }
    summin=min(summin,sum);
  }
  return summin;
}
int main()
{
  FILE*fin,*fout;
  fin=fopen("tribute.in","r");
  fout=fopen("tribute.out","w");
  long long n,dx,dy;
  fscanf(fin,"%lld%lld%lld",&n,&dx,&dy);
  for(long long i=1;i<=n;i++){
    fscanf(fin,"%lld%lld",&ln[i],&cl[i]);
  }
  sort(ln+1,ln+n+1);
  sort(cl+1,cl+n+1);
  fprintf(fout,"%lld",solve(n,ln,dx+2)+solve(n,cl,dy+2));
  return 0;
}