Cod sursa(job #1472928)

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

constexpr int maxn = 50001;

long long rezolva_2d(const array<int, maxn>& v, const int d, const int max_poz){
	int nr_st = 0, nr_dr = accumulate(begin(v)+d+1, end(v), 0);
	long long cost_cur = 0;
	for(int i = d+1; i < maxn; ++i){
		cost_cur += v[i] * (i-d); }
	long long cost_min = cost_cur;
	for(int st = 1, dr = d+1; dr < maxn; ++st, ++dr){
		nr_st += v[st-1];
		cost_cur += nr_st;
		cost_cur -= nr_dr;
		nr_dr -= v[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];
		max_x = max(max_x, x);
		max_y = max(max_y, y); }
	g << (rezolva_2d(poz_x, dx, max_x) + rezolva_2d(poz_y, dy, max_y));
	return 0; }