Cod sursa(job #2769500)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 16 august 2021 10:49:06
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("tribute.in");
ofstream fout("tribute.out");

const int nmax = 50005;
int n, dx, dy, sum1[nmax][2], sum2[nmax][2];
vector <int> v1, v2;

int solve(vector <int> &v, int d){
    memset(sum1, 0, sizeof sum1);
    memset(sum2, 0, sizeof sum2);
    sort(v.begin(), v.end());
    int minim = 1e9;
    for (int i = 0; i < n; ++i){
        sum1[v[i]][0]++;
        sum2[v[i]][0]++;
        sum1[v[i]][1] += v[i];
        sum2[v[i]][1] += v[i];
    }
    for (int i = 1; i <= 50000; ++i){
        sum1[i][0] += sum1[i - 1][0];
        sum1[i][1] += sum1[i - 1][1];
    }
    for (int i = 50000; i >= 0; --i){
        sum2[i][0] += sum2[i + 1][0];
        sum2[i][1] += sum2[i + 1][1];
    }
    for (int i = 0; i + d <= 50000; ++i){
        int m = 0;
        m = m + sum2[i + d + 1][1] - (i + d) * sum2[i + d + 1][0];
        m = m + i * sum1[i][0] - sum1[i][1];
        minim = min(minim, m);
    }
    return minim;
}

int main(){
    fin >> n >> dx >> dy;
    for (int i = 1; i <= n; ++i){
        int x, y;
        fin >> x >> y;
        v1.push_back(x);
        v2.push_back(y);
    }
    fout << solve(v1, dx) + solve(v2, dy);
    return 0;
}