Cod sursa(job #2736325)

Utilizator LeCapataIustinian Serban LeCapata Data 3 aprilie 2021 12:55:19
Problema Tribute Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <algorithm>
#define N 50005
using namespace std;

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

struct coord{
    int x, y;
}punct[N];

struct baliere{
    long long sumStg[N], sumDrp[N];
    int cate[N];
}X, Y;

int n, dx, dy, minX = N, minY = N, maxX, maxY;
int fx[N], fy[N];

int main()
{
    in>>n>>dx>>dy;

    for(int i = 1; i <= n; ++i){
        in>>punct[i].x>>punct[i].y;
        fx[punct[i].x]++;
        fy[punct[i].y]++;

        minX = min(minX, punct[i].x);
        minY = min(minY, punct[i].y);

        maxX = max(maxX, punct[i].x);
        maxY = max(maxY, punct[i].y);
    }

    X.cate[minX] = fx[minX];
    for(int i = minX + 1; i <= maxX + dx; ++i){
        X.sumStg[i] = X.sumStg[i - 1] + X.cate[i - 1];
        X.cate[i] = X.cate[i - 1] + fx[i];
    }
    X.cate[maxX] = fx[maxX];
    for(int i = maxX - 1; i >= minX; --i){
        X.sumDrp[i] = X.sumDrp[i + 1] + X.cate[i + 1];
        X.cate[i] = X.cate[i + 1] + fx[i];
    }

    Y.cate[minY] = fy[minY];
    for(int i = minY + 1; i <= maxY + dy; ++i){
        Y.sumStg[i] = Y.sumStg[i - 1] + Y.cate[i - 1];
        Y.cate[i] = Y.cate[i - 1] + fy[i];
    }

    Y.cate[maxY] = fy[maxY];
    for(int i = maxY - 1; i >= minY; --i){
        Y.sumDrp[i] = Y.sumDrp[i + 1] + Y.cate[i + 1];
        Y.cate[i] = Y.cate[i + 1] + fy[i];
    }

    long long solX = N, solY = N;

    for(int i = minX; i <= maxX + dx; ++i)
        solX = min(solX, (X.sumStg[i] - X.sumStg[minX]) + (X.sumDrp[i + dx] - X.sumDrp[maxX]));

    for(int i = minY; i <= maxY + dy; ++i)
        solY = min(solY, (Y.sumStg[i] - Y.sumStg[minY]) + (Y.sumDrp[i + dy] - Y.sumDrp[maxY]));

    out<<solX + solY;

    in.close();
    out.close();
    return 0;
}