Cod sursa(job #2644706)

Utilizator RaresFelixTudose Rares Felix RaresFelix Data 25 august 2020 17:29:59
Problema Tribute Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<pair<int,int> > vii;

ifstream fi("tribute.in");
ofstream fo("tribute.out");

int n,dx,dy,a,b,X[100005],Y[100005];
int re1,re2,optimx,optimy;
int calc_x()
{
    ///calculam costul daca luam segmentul 0,dx ca ok
    int cost=0,dr=0,st=0,minim = 0,loc = 0;
    for(int i=dx+1;i<n;i++){
        dr+=X[i];
        cost+=X[i]*(i-dx);
    }
    minim = cost;
    ///incercam segmentele i,dx+i
    for(int i=1;i<n-dx+2;i++){
        //adaugam la stanga i-1
        st+=X[i-1];
        //adaugam st la cost
        cost += st;

        //scadem dr din cost
        cost-=dr;
        //scadem ce prinem in dx+i
        dr-=X[dx+i];

        if(minim>cost){
            loc = i;
            minim = cost;
        }
    }
    return minim;
}
int calc_y()
{
    ///calculam costul daca luam segmentul 0,dy ca ok
    int cost=0,dr=0,st=0,minim = 0,loc = 0;
    for(int i=dy+1;i<n;i++){
        dr+=Y[i];
        cost+=Y[i]*(i-dy);
    }
    minim = cost;
    ///incercam segmentele i,dx+i
    for(int i=1;i<n-dy+2;i++){
        //adaugam la stanga i-1
        st+=Y[i-1];
        //adaugam st la cost
        cost += st;

        //scadem dr din cost
        cost-=dr;
        //scadem ce prinem in dx+i
        dr-=Y[dy+i];
        if(minim>cost){
            loc = i;
            minim = cost;
        }
    }
    return minim;
}
int main()
{
    ///cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    fi>>n>>dx>>dy;
    for(int i=1;i<=n;i++){
        fi>>a>>b;
        X[a]++;Y[b]++;
    }
    fo<<calc_x()+calc_y();
    return 0;
}