Cod sursa(job #2627428)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 10 iunie 2020 17:23:52
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[2][50005], D[2], n, S, rez, x, y;

int main() {
	fin >> n >> D[0] >> D[1];
	for(int i = 0; i < n; ++i) {
		fin >> x >> y;
		++v[0][x]; ++v[1][y];
	}

	/*for(int i = 1; i <= 50000; ++i) {
		v[0][i] += v[0][i-1];
		v[1][i] += v[1][i-1];
	}*/

	for(int k = 0; k < 2; ++k) {
		int curl = 0, curr = 0, ptl = 0, ptr = 0;
		for(int i = D[k]+1; i <= 50000; ++i)
			if(v[k][i]) {
				ptr += v[k][i];
				curr += (i - D[k]) * v[k][i];
			}
		ptl = v[k][0];
		rez = curr; //cout << rez << "/";
		for(int i = 1; i + D[k] <= 50000; ++i) {
			curl += ptl; ptl += v[k][i];
			curr -= ptr; ptr -= v[k][i+D[k]];
			rez = min(rez, curl+curr);
		}
		S += rez; //cout << rez << endl;
	}

	fout << S;
	return 0;
}