Cod sursa(job #3355687)

Utilizator rares89_Dumitriu Rares rares89_ Data 24 mai 2026 23:20:11
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

long long solve(vector<long long>& v, long long D) {
    int n = v.size();
    sort(v.begin(), v.end());
    
    vector<long long> s(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        s[i + 1] = s[i] + v[i];
    }
    
    long long ans = -1;
    for (int i = 0; i < n; ++i) {
        long long cands[2] = {v[i], v[i] - D};
        for (long long x : cands) {
            int p1 = lower_bound(v.begin(), v.end(), x) - v.begin();
            int p2 = upper_bound(v.begin(), v.end(), x + D) - v.begin();
            
            long long cost = (1LL * p1 * x - s[p1]) + ((s[n] - s[p2]) - 1LL * (n - p2) * (x + D));
            
            if (ans == -1 || cost < ans) {
                ans = cost;
            }
        }
    }
    return ans;
}

int main() {
    int n;
    long long dx, dy;
    fin >> n >> dx >> dy;
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        fin >> x[i] >> y[i];
    }
    fin.close();
    
    fout << solve(x, dx) + solve(y, dy) << "\n";
    
    return 0;
}