Cod sursa(job #2886924)

Utilizator lolismekAlex Jerpelea lolismek Data 8 aprilie 2022 16:45:00
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 5e4, inf = 1e9;
int x[N + 1], y[N + 1], dx[N + 1], dy[N + 1];

int main(){
	int n, L, C;
	fin >> n >> L >> C;

	for(int i = 1; i <= n; i++){
		int a, b;
		fin >> a >> b;
		x[b]++, y[a]++;
	}

	int front, back;

	// pe linii:

	front = back = 0;
	for(int i = N; i > L; i--)
		dx[L] += x[i] * (i - L), front += x[i];
	

	for(int i = L + 1; i <= N; i++){
		back += x[i - L - 1];
		dx[i] = dx[i - 1] - front + back;
		front -= x[i];
	}

	// pe coloane:

	front = back = 0;
	for(int i = N; i > C; i--)
		dy[C] += y[i] * (i - C), front += y[i];
	
	for(int i = C + 1; i <= N; i++){
		back += y[i - C - 1];
		dy[i] = dy[i - 1] - front + back;
		front -= y[i];
	}

	int ansx = inf;
	for(int i = L; i <= N; i++)
		ansx = min(ansx, dx[i]);

	int ansy = inf;
	for(int i = C; i <= N; i++)
		ansy = min(ansy, dy[i]);

	fout << ansx + ansy;
	return 0;
}