# Cod sursa(job #1882755)

Utilizator Data 17 februarie 2017 14:20:52 Ferma2 100 cpp done Arhiva de probleme 1.44 kb
``````#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

const int kMaxDim = 1005;

int a[kMaxDim][kMaxDim];
int sumLine[kMaxDim][kMaxDim], sumColumn[kMaxDim][kMaxDim], sumDiagonal[kMaxDim][kMaxDim];

int main() {
std::ifstream inputFile("ferma2.in");
std::ofstream outputFile("ferma2.out");

int n, k;
inputFile >> n >> k;

int totalSum = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j) {
inputFile >> a[i][j];

totalSum += a[i][j];
sumLine[i][j] = a[i][j] + sumLine[i][j - 1];
sumColumn[i][j] = a[i][j] + sumColumn[i - 1][j];
sumDiagonal[i][j] = a[i][j] + sumDiagonal[i - 1][j - 1];
}

int size = n - k;

if (size == 0) {
outputFile << totalSum << '\n';
return 0;
}

int minSum = 0;
for (int i = 1; i <= size; ++i)
minSum += sumLine[i][i];

int startSum = minSum;
for (int i = 2; i + size - 1 <= n; ++i) {
startSum += sumLine[i + size - 1][size];
startSum -= sumDiagonal[i - 1 + size - 1][1 + size - 1];

int currSum = startSum;
minSum = std::min(minSum, currSum);

for (int j = 2; j <= i; ++j) {
currSum += sumDiagonal[i + size - 1][j + size - 1] - sumDiagonal[i - 1][j - 1];
currSum -= sumColumn[i + size - 1][j - 1] - sumColumn[i - 1][j - 1];

minSum = std::min(minSum, currSum);
}
}

outputFile << totalSum - minSum << '\n';

inputFile.close();
outputFile.close();

return 0;
}

//Trust me, I'm the Doctor!
``````