Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2303
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2303
Margaridas
Por OBI - Olimpíada Brasileira de Informática 2006 
Brazil
Timelimit: 1
Leopoldo é gerente de uma plantação de flores da Associação de Cultivo de Margaridas (ACM), um grupo que cultiva margaridas em grandes propriedades para abastecer floriculturas em grandes cidades.
As margaridas são plantadas em vasos dispostos em linhas e colunas, formando uma espécie de grade. Na plantação administrada por Leopoldo existem L linhas de vasos de margaridas, cada uma formada por C vasos. Para facilitar o gerenciamento, os vasos são organizados em lotes de M linhas e N colunas de vasos, sendo que não existem sobreposições entre os lotes (não existe nenhuma linha ou coluna comum a mais de um lote) e todos os lotes têm exatamente M linhas e N colunas.
A colheita é sempre feita em um único lote, coletando-se todas as margaridas daquele lote que estejam prontas para a venda. Uma semana antes de fazer a colheita, os funcionários da plantação analisaram cada vaso e anotaram quantas margaridas estarão prontas para venda na semana seguinte. Leopoldo agora precisa da sua ajuda para determinar qual o número máximo de margaridas que poderá ser colhido em um único lote de M × N vasos.
Sua tarefa é escrever um programa que, dado um mapa da plantação contendo o número de margaridas prontas para venda em cada vaso, encontre qual o número máximo de margaridas que podem ser colhidos por Leopoldo.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém quatro números inteiros, L, C, M e N. L e C representam respectivamente o número de linhas (1 ≤ L ≤ 1000) e de colunas (1 ≤ C ≤ 1000) de vasos existentes na plantação. M e N representam respectivamente o número de linhas (1 ≤ M ≤ L) e de colunas (1 ≤ N ≤ C) dos lotes. As L linhas seguintes contêm C inteiros cada, representando número de margaridas prontas para colheita no vaso localizado naquela linha e coluna. Note que L M e C N são sempre inteiros, pois não há linha ou coluna de vasos que pertença a mais de um lote.
Saída
Seu programa deve imprimir, na saída padrão, uma única linha que contém o número máximo de margaridas que podem ser colhidos em um lote de M × N. Esse número não pode ser superior a 1000000.
| Exemplos de Entrada | Exemplos de Saída |
|
3 3 1 1 1 2 3 1 3 3 1 10 1 |
10 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 1e3 + 1;
int matriz[MAXN][MAXN], soma[MAXN][MAXN], resp, n, m, p, q;
int main() {
scanf("%d %d %d %d", &n, &m, &p, &q);
for (int linha = 1; linha < = n; linha++) {
for (int coluna = 1; coluna < = m; coluna++) {
scanf("%d", &matriz[linha][coluna]);
soma[linha][coluna] =
soma[linha][coluna - 1] + matriz[linha][coluna];
}
}
for (int linha = 1; linha + p - 1 < = n; linha += p) {
for (int coluna = 1; coluna + q - 1 < = m; coluna += q) {
int colunafim = coluna + q - 1;
int colunaini = coluna - 1;
int linhalimite = linha + p - 1;
int temp = 0;
for (int linhadavez = linha; linhadavez < = linhalimite;
linhadavez++) {
temp +=
soma[linhadavez][colunafim] - soma[linhadavez][colunaini];
}
// printf("Linha %d Coluna %d Colunafim %d Colunaini %d Linhalimite
// %d Temp %d Resp
// %d\n",linha,coluna,colunafim,colunaini,linhalimite,temp,resp);
resp = max(temp, resp);
}
}
printf("%d\n", resp);
return 0;
}
Input
1 2 3
1 3 3
1 10 1
Output