Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2305

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2305

Colheita de Caju

 

Por OBI - Olimpíada Brasileira de Informática 2006 BR Brazil

Timelimit: 1

Conrado é gerente em uma das fazendas de plantação de caju da Sociedade de Beneficiamento de Caju (SBC), um grupo que cultiva caju em grandes propriedades para o mercado externo.

Os cajueiros são plantados dispostos em linhas e colunas, formando uma espécie de grade. Na fazenda administrada por Conrado existem L linhas de cajueiros, cada uma formada por C colunas. Nesta semana Conrado deve executar a colheita da produção de um subconjunto contínuo de cajueiros. Esse subconjunto é formado por M linhas e N colunas de cajueiros. Há uma semana, seus funcionários analisaram cada cajueiro da fazenda e estimaram a sua produtividade em número de cajus prontos para a colheita. Conrado agora precisa da sua ajuda para determinar qual a produtividade máxima estimada (em número de cajus) de uma área de M × N cajueiros.

Sua tarefa é escrever um programa que, dado um mapa da fazenda contendo o número de cajus prontos para colheita em cada cajueiro, encontre qual o número máximo de cajus que podem ser colhidos na fazenda em uma área de M × N cajueiros.

 

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 cajueiros existentes na fazenda. M e N representam, respectivamente, o número de linhas (1 ≤ ML) e de colunas (1 ≤ NC) de cajueiros a serem colhidos. As L linhas seguintes contêm C inteiros cada, representando número de cajus prontos para colheita no cajueiro localizado naquela linha e coluna.

 

Saída

 

Seu programa deve imprimir, na saída padrão, uma única linha que contém o número máximo estimado de cajus que podem ser colhidos em uma área contínua de M × N. Esse número não 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];
        }
    }
    p = min(p, n);
    q = min(m, q);
    for (int linha = 1; linha + p - 1  < = n; linha++) {
        for (int coluna = 1; coluna + q - 1  < = m; coluna++) {
            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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 3 1 1
1 2 3
1 3 3
1 10 1

Output

x
+
cmd
10
Advertisements

Demonstration


Previous
#2304 Beecrowd Online Judge Solution 2304 Banco Imobiliário Solution in C, C++, Java, Js and Python
Next
#2308 Beecrowd Online Judge Solution 2308 Museu Solution in C, C++, Java, Js and Python