Cod sursa(job #1528135)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 19 noiembrie 2015 09:04:27
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;

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

double largest_sum_wider_than(const vector<double>& v, const int min_len, const int max_len){
	const int n = v.size();
	vector<double> s_part(n+1, 0);

	double rez = -1000000000;
	auto sort_by_s_part = [&s_part](const int a, const int b){
		return s_part[a] < s_part[b]; };

	my_deque<decltype(sort_by_s_part)> dq(sort_by_s_part);

	for(int i = 0; i < n; ++i){
		s_part[i+1] = s_part[i] + v[i];
		if(i-min_len+1 >= 0){
			dq.push(i-min_len+1);
			rez = max(rez, s_part[i+1] - s_part[dq.front()]); }
		dq.pop(i-max_len); }
	return rez; }

double largest_submat(const vector<vector<double> >& v, const int min_r, const int max_r, const int min_c, const int max_c){
	const int r = v.size(), c = v[0].size();
	vector<vector<double> > s_part_col(r+1, vector<double>(c, 0));
	for(int i = 0; i < r; ++i){
		for(int j = 0; j < c; ++j){
			s_part_col[i+1][j] = s_part_col[i][j] + v[i][j]; } }
	
	vector<double> un_rand(c, 0);
	double rez = -1000000000;
	for(int i = 0; i+min_r <= r; ++i){
		for(int j = i+min_r; j <= r && j <= i+max_r; ++j){
			for(int k = 0; k < c; ++k){
				un_rand[k] = s_part_col[j][k] - s_part_col[i][k]; }
			rez = max(rez, largest_sum_wider_than(un_rand, min_c, max_c)); } }
	return rez; }

double cbin(vector<vector<double> >& v, const int min_r, const int max_r, const int min_c, const int max_c){
	double st = 0, dr = 100000, to_add = 0;
	for(int i = 0; i < 30; ++i){
		double mij = st + (dr-st)/2;
		{
			double delta = to_add-mij;
			for(auto& y : v){
				for(auto& x : y){
					x += delta; } }
			to_add = mij; }
		if(largest_submat(v, min_r, max_r, min_c, max_c) >= 0){
			st = mij; }
		else{
			dr = mij; } }
	return st; }

int main(){
	ifstream f("balans.in");
	ofstream g("balans.out");
	int n, m, r, c;
	f >> n >> m >> r >> c;
	vector<vector<double> > v(2*n, vector<double>(2*m, 0));
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			f >> v[i][j];
			v[i+n][j] = v[i][j+m] = v[i+n][j+m] = v[i][j]; } }
	g << fixed << setprecision(3) << cbin(v, r, n, c, m);
	return 0; }