Cod sursa(job #2783650)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 14 octombrie 2021 20:33:22
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#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;
}