Pagini recente » Cod sursa (job #1622981) | Cod sursa (job #1873307) | Cod sursa (job #1329503) | Cod sursa (job #1991069) | Cod sursa (job #1489142)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iomanip>
#include <deque>
#define DIM 305
#define infile "balans.in"
#define outfile "balans.out"
using namespace std;
ofstream fout(outfile);
int n, m, r, c;
int a[DIM][DIM];
long long partialColumnSum[DIM][DIM], aux[DIM];
deque<int> deq;
//The Parser class can be used to optimize the reading of data from a specified path (or with little changes from the console)
class Parser {
private:
char *buffer; //a string containing a contiguos array of chars from the input file, from this the numerical data would be extracted
int maxLenBuffer; //the maximum length of the buffer
int currentBufferIndex; //the current position in the buffer being processed
std::fstream file; //the stream used to accesses the path
public:
//no default constructor because the file path and the maxLenBuffer are relevant
Parser(std::string path, int maxLenBuffer) {
this->maxLenBuffer = maxLenBuffer;
this->file.open(path, std::ios::in);
buffer = new char[maxLenBuffer];
//we read the first piece of data
file.get(buffer, maxLenBuffer, EOF);
//we set the cursor at position 0
this->currentBufferIndex = 0;
}
//the Parser allows reading any integer numerical type: int, short, long long and their unsigned type
template<class classType>
void readNumber(classType &number) {
number = 0;
int sign = 1; //for positive/negative numbers;
char prevChar = 0; //keeps the last processed char
//skips unusable chars
while (buffer[currentBufferIndex] < '0' || buffer[currentBufferIndex] > '9') {
prevChar = buffer[currentBufferIndex];
//next char
++currentBufferIndex;
//if the buffer ends we need to read again in case there is more data in the file
if (currentBufferIndex == maxLenBuffer - 1) {
file.get(buffer, maxLenBuffer, EOF);
currentBufferIndex = 0;
}
}
if (prevChar == '-')
sign = -1;
//here the number is built
while (buffer[currentBufferIndex] >= '0' && buffer[currentBufferIndex] <= '9') {
number = number * 10 + (buffer[currentBufferIndex] - '0');
//next char
++currentBufferIndex;
//if the buffer ends we need to read again in case there is more data in the file
if (currentBufferIndex == maxLenBuffer - 1) {
file.get(buffer, maxLenBuffer, EOF);
currentBufferIndex = 0;
}
}
if (buffer[currentBufferIndex] == '.') {
//next char
++currentBufferIndex;
//if the buffer ends we need to read again in case there is more data in the file
if (currentBufferIndex == maxLenBuffer - 1) {
file.get(buffer, maxLenBuffer, EOF);
currentBufferIndex = 0;
}
classType fractionalExponent = 0.1; //with this we contruct the fractional part of the number
while (buffer[currentBufferIndex] >= '0' && buffer[currentBufferIndex] <= '9') {
number = number + fractionalExponent * (buffer[currentBufferIndex] - '0');
fractionalExponent /= 10.0;
//next char
++currentBufferIndex;
//if the buffer ends we need to read again in case there is more data in the file
if (currentBufferIndex == maxLenBuffer - 1) {
file.get(buffer, maxLenBuffer, EOF);
currentBufferIndex = 0;
}
}
}
//puts the right sign to the number
number *= sign;
}
//closes the file when an instance of this class is deleted
~Parser() {
file.close();
}
};
bool check(int value) {
for (int upRow = 1; upRow <= n; ++upRow) {
for (int downRow = upRow + r - 1; downRow - upRow + 1 <= n; ++downRow) {
for (int column = 1; column <= 2 * m; ++column) {
aux[column] = aux[column - 1] + partialColumnSum[downRow][column] - partialColumnSum[upRow - 1][column] - 1LL * value * (downRow - upRow + 1);
}
deq.clear();
for (int column = c; column <= 2 * m; ++column) {
while (!deq.empty() && aux[column - c] <= aux[deq.back()])
deq.pop_back();
deq.push_back(column - c);
if (deq.front() < column - m)
deq.pop_front();
if (aux[column] - aux[deq.front()] >= 0)
return true;
}
}
}
return false;
}
int main() {
Parser *parser = new Parser(infile, 4000000);
parser->readNumber(n);
parser->readNumber(m);
parser->readNumber(r);
parser->readNumber(c);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
parser->readNumber(a[i][j]);
a[i + n][j] = a[i + n][j + n] = a[i][j + n] = a[i][j] = a[i][j] * 1000;
}
}
for (int i = 1; i <= 2 * n; ++i) {
for (int j = 1; j <= 2 * m; ++j) {
partialColumnSum[i][j] = partialColumnSum[i - 1][j] + a[i][j];
}
}
int solution = 0;
for (int bit = (1 << 30); bit; bit >>= 1) {
if (check(solution | bit)) {
solution |= bit;
}
}
fout << setprecision(3) << fixed << solution / 1000.0;
return 0;
}
//Trust me, I'm the Doctor!