Cod sursa(job #1472929)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 18 august 2015 07:57:17
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <iostream>
#include <array>
#include <algorithm>
#include <cassert>
using namespace std;

constexpr int maxn = 50001;

unsigned int rezolva_2d(const array<int, maxn>& v, const int d){
	int nr_magic = accumulate(begin(v)+d+1, end(v), 0);
		// in revizia trecuta am avut nr_st, nr_dr
		// nr_magic = nr_dr - nr_st;
	unsigned int cost_cur = 0;
	for(int i = d+1; i < maxn; ++i){
		cost_cur += v[i] * (i-d); }
	unsigned int cost_min = cost_cur;
	for(auto st = begin(v), dr = begin(v)+d+1; dr != end(v); ++st, ++dr){
		nr_magic -= *st;
		cost_cur -= nr_magic;
		nr_magic -= *dr;
		cost_min = min(cost_min, cost_cur); }
	return cost_min; }

int main(){
	ifstream f("tribute.in");
	ofstream g("tribute.out");
	int n, dx, dy;
	f >> n >> dx >> dy;
	array<int, maxn> poz_x, poz_y;
	for(auto& x : poz_x){
		x = 0; }
	for(auto& y : poz_y){
		y = 0; }
	int max_x = 0, max_y = 0;
	for(int i = 0, x, y; i < n; ++i){
		f >> x >> y;
		++poz_x[x];
		++poz_y[y]; }
	g << ((long long)(rezolva_2d(poz_x, dx)) + rezolva_2d(poz_y, dy));
	return 0; }