Cod sursa(job #2508892)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 13 decembrie 2019 12:23:20
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 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 sumsuf=0,sumpref=0,summin=1<<30;
  long long cost=0;
  for(long long i=n;i>=1;i--){
    cost+=v[i];
  }
  long long st=0,dr=0,val=0;
  while(dr<=n && v[dr+1]<=r){
    dr++;
  }
  cost-=(n-dr)*r;
  summin=cost;
  for(val=1;val<=v[n];val++){
    while(st<=n && v[st+1]<val){
      st++;
    }
    cost+=st;
    cost-=(n-st);
    /*while(dr<=n && v[dr+1]<=val+r){
      dr++;
    }*/
    summin=min(summin,sumpref+sumsuf-r*(v[st]+r));
  }
  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)+solve(n,cl,dy));
  return 0;
}