Cod sursa(job #1528223)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 19 noiembrie 2015 11:58:07
Problema Balans Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
#include <deque>
#include <limits>
#include <array>
using namespace std;

constexpr int nmax = 400;

bool exista_subsecv_poz(const array<long long, nmax>& s_part, const int n, const int min_len, const int max_len){

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


	vector<int> dq(n, -1);
	int st = 0, dr = n-1;

	for(int i = 0; i < n; ++i){
		if(dq[st] == i-max_len-1){
			dq[st] = -1;
			++st;
			if(st >= n){
				st -= n; } }

		if(i-min_len >= 0){
			while(dq[dr] != -1 && s_part[dq[dr]] >= s_part[i-min_len-1]){
				dq[dr] = -1;
				--dr;
				if(dr < 0){
					dr += n; } }
			++dr;
			if(dr >= n){
				dr -= n; }
			dq[dr] = i-min_len;

			if(dq[st] != -1 && s_part[i] >= s_part[dq[st]]){
				return true; } } }

	return false; }

bool exista_submat_poz(const array<array<int, nmax>, nmax>& v, const int r, const int c, const int min_r, const int max_r, const int min_c, const int max_c, const long long delta){
	array<long long, nmax> s_part_col;

	for(int i = 0; i+min_r <= r; ++i){
		cout << i << endl;
		fill(begin(s_part_col), end(s_part_col), 0);
		for(int j = i; j < r && j-i <= max_r; ++j){

			long long la_stanga = 0;
			for(int k = 1; k <= c; ++k){
				la_stanga += v[j][k-1];
				la_stanga -= delta;
				s_part_col[k] += la_stanga; }
			
			if(j-i+1 >= min_r && exista_subsecv_poz(s_part_col, c, min_c, max_c)){
				return true; } } }
	return false; }

int cbin(const array<array<int, nmax>, nmax>& v, const int r, const int c, const int min_r, const int max_r, const int min_c, const int max_c){
	long long st = 0, dr = 1000010000;
	for(int step = 1ll<<(int)log2(dr-st+1); step > 0; step /= 2){
		if(st+step <= dr){
			if(exista_submat_poz(v, r, c, min_r, max_r, min_c, max_c, st+step)){
				st += step; } } }
	return st; }

int main(){
	ifstream f("balans.in");
	ofstream g("balans.out");
	int n, m, r, c;
	f >> n >> m >> r >> c;

	if(r == 0){
		r = 1; }
	if(c == 0){
		c = 1; }

	array<array<int, nmax>, nmax> v;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			f >> v[i][j];
			v[i][j] *= 1000;
			v[i+n][j] = v[i][j+m] = v[i+n][j+m] = v[i][j]; } }

	const int rez = cbin(v, 2*n, 2*m, r, n, c, m);

	g << fixed << setprecision(3) << rez/1000 << '.' << setw(3) << setfill('0') << rez%1000 << '\n';
	return 0; }