Cod sursa(job #2508883)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 13 decembrie 2019 11:50:04
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005;
int ln[N],cl[N];
int solve(int n,int v[],int r){
  int sum=0,summin=1<<30;
  for(int i=1;i<=n;i++){
    sum+=v[i];
  }
  int 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");
  int n,dx,dy;
  fscanf(fin,"%d%d%d",&n,&dx,&dy);
  for(int i=1;i<=n;i++){
    fscanf(fin,"%d%d",&ln[i],&cl[i]);
  }
  sort(ln+1,ln+n+1);
  sort(cl+1,cl+n+1);
  fprintf(fout,"%d",solve(n,ln,dx+2)+solve(n,cl,dy+2));
  return 0;
}