Cod sursa(job #1489731)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 21 septembrie 2015 22:15:34
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
#include <iomanip>
using namespace std;

constexpr double epsilon = 1e-4;

void mk_partial_sums(const vector<vector<double> >& v,
	vector<vector<double> >& rez){
	const int n = v.size(), m = v.front().size();
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			rez[i][j] =
				v[i-1][j-1] +
				rez[i-1][j] +
				rez[i][j-1] -
				rez[i-1][j-1]; } } }

template <typename Cmp>
class min_deque{
	deque<int> dq;
	Cmp c;
public:
	min_deque(const Cmp cc): c(cc){}
	void push(const int x){
		while(!dq.empty() && !c(dq.back(), x)){
			dq.pop_back(); }
		dq.push_back(x); }
	int front(){
		return dq.front(); }
	void pop(const int x){
		if(!dq.empty() && dq.front() == x){
			dq.pop_front(); } } };

bool exista_subsecv_suma_pozitiva(const vector<double>& s_part, const int c, const int C){
	auto cmp = [s_part](const int a, const int b){
		return s_part[a] < s_part[b]; };
	min_deque<decltype(cmp)> dq(cmp);
	for(int i = c; i < s_part.size(); ++i){
		dq.push(i-c);
		if(s_part[i] - s_part[dq.front()] >= -epsilon){
			return true; }
		dq.pop(i-C); }
	return false; }

bool exista_submat_suma_pozitiva(
	const vector<vector<double> >& v, const int r, const int c, const int R, const int C){

	const int n = v.size(), m = v.front().size();

	static vector<vector<double> > sume_part(v.size()+1, vector<double>(v[0].size()+1, 0));
	static vector<double> sume_part_linie(v[0].size()+1, 0);
	mk_partial_sums(v, sume_part);

	for(int i = 0; i < n; ++i){
		for(int j = i+r; j <= i+R && j <= n; ++j){
			transform(begin(sume_part[j]), end(sume_part[j]), begin(sume_part[i]),
				begin(sume_part_linie), minus<double>());
			if(exista_subsecv_suma_pozitiva(sume_part_linie, c, C)){
				return true; } } }
			
	return false; }

bool check(const vector<vector<int> >& mat, const double d, const int r, const int c, const int R, const int C){
	static vector<vector<double> > m(mat.size(), vector<double>(mat[0].size(), 0));

	for(int i = 0; i < mat.size(); ++i){
		for(int j = 0; j < mat[i].size(); ++j){
			m[i][j] = mat[i][j] - d; } }
	return exista_submat_suma_pozitiva(m, r, c, R, C); }

double bin_search(const vector<vector<int> >& v, const int r, const int c, const int R, const int C){
	double st, dr, mij;
	for(st = 0, dr = 100000; st+epsilon < dr; ){
		mij = st + (dr-st)/2;
		if(check(v, mij, r, c, R, C)){
			st = mij; }
		else{
			dr = mij; } }
	return st; }

void citeste(vector<vector<int> >& v, int& r, int& c){
	ifstream f("balans.in");
	int n, m;
	f >> n >> m >> r >> c;
	if(n <= m){
		v.resize(2*n, vector<int>(2*m));
		for(int i = 0, di = n; i < n; ++i, ++di){
			for(int j = 0, dj = m; j < m; ++j, ++dj){
				f >> v[i][j];
				v[i][dj] = v[di][j] = v[di][dj] = v[i][j]; } } }
	else{
		swap(n, m);
		swap(r, c);
		v.resize(2*n, vector<int>(2*m));
		for(int j = 0, dj = m; j < m; ++j, ++dj){
			for(int i = 0, di = n; i < n; ++i, ++di){
				f >> v[i][j];
				v[i][dj] = v[di][j] = v[di][dj] = v[i][j]; } } } }

int main(){
	vector<vector<int> > v;
	int r, c;
	citeste(v, r, c);
	ofstream g("balans.out");
	g << fixed << setprecision(3) <<
		bin_search(v, r, c, v.size()/2, v[0].size()/2);
	return 0; }