Question

A. Матрицы ограничение по времени на тест1 секунда ограничение по памяти на тест256 мегабайт вводстандартный ввод выводстандартный вывод Вам дана матрица размера N×M, состоящая из целых положительных чисел, а также целое число K. Назовем подматрицу хорошей, если она является квадратом и сумма этой подматрицы не больше K. Посчитайте количество хороших подматриц. Подматрицей называется такая матрица, которую можно получить из исходной, если удалить из нее несколько(возможно ноль) столбцов с левого и правого края, а также несколько(возможно ноль) строк с верхнего и нижнего края. При этом подматрица не должна быть пустой. Входные данные В первой строке заданы 3 целых числа N, M, K — размеры матрицы. (1≤N,M≤1500, 0≤K≤109) В следующих N строках содержится по M целых положительных чисел — содержимое матрицы (числа по значению от 1 до 1000). Выходные данные Выведите одно число — количество подходящих подматриц. Система оценки Данная задача содержит 6 подзадач, в которых выполняются следующие ограничения: Тесты из условия. Оценивается в 0 баллов. N,M≤2. Оценивается в 15 баллов. N,M≤100. Оценивается в 17 баллов. N,M≤500. Оценивается в 24 балла. N,M≤1500 и матрица состоит только из единичек. Оценивается в 15 баллов. Исходные ограничения. Оценивается в 29 баллов. входные данные 3 3 12 1 2 3 5 2 5 3 2 4 Выходные данные 12 входные данные 6 6 30 4 4 4 1 1 1 2 5 5 3 2 3 3 2 2 4 1 3 1 1 4 4 4 5 1 3 3 4 5 5 2 5 5 4 3 4 выходные данные 71

Answer 1

#include <bits/stdc++.h>

#define no cout << "NO" << endl

#define yes cout << "YES" << endl

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)

typedef long long ll;

const int MAXN = 2e5 + 5;

const ll mod = 1e9 + 7;

 

using namespace std;

int n, m, k;

int cnt = 0, v, b[MAXN], ans = 0, sum;

int main() {

   fast;

cout << "im retarded";

}

Answer 2

from random import random

M = 3

N = 3

a = []

w = 0

for i in range(N):

   b = []

   for j in range(M):

       b.append(int(random()*11))

       print("%3d" % b[j], end='')

   w = w + sum(b)

   a.append(b)

   print('   |', sum(b))

 

for i in range(M):

   print(" --", end='')

print()

 

for i in range(M):

   s = 0

   for j in range(N):

       s += a[j][i]

   print("%3d" % s, end='')

print()

print('Выходные данные: ', w)

Answer 3

Для решения этой задачи можно воспользоваться динамическим программированием. Для каждой ячейки матрицы (i, j) будем подсчитывать, сколько подматриц, заканчивающихся в этой ячейке, соответствуют условиям задачи. Для этого будем хранить два дополнительных массива: сумму элементов в каждом столбце слева от текущей ячейки и минимальную сумму элементов в подматрице, заканчивающейся в текущей ячейке. Затем, для каждой ячейки (i, j), можно определить размер самой большой квадратной подматрицы с суммой не больше K, заканчивающейся в этой ячейке, и добавить это количество к ответу.

Вот Python-код, решающий эту задачу:

pythonCopy code
N, M, K = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

# Дополнительные массивы для хранения сумм и минимальных сумм
column_sums = [[0] * M for _ in range(N)]
min_submatrix_sums = [[0] * M for _ in range(N)]

# Заполняем суммы столбцов и минимальные суммы подматриц
for i in range(N):
    for j in range(M):
        column_sums[i][j] = matrix[i][j] + (column_sums[i - 1][j] if i > 0 else 0)
        min_submatrix_sums[i][j] = matrix[i][j] + (min_submatrix_sums[i - 1][j] if i > 0 else 0)

# Функция для проверки, можно ли увеличить размер подматрицы
def can_increase_size(i, j, size):
    if i - size < 0 or j - size < 0:
        return False
    sum_of_submatrix = column_sums[i][j] - (column_sums[i - size][j] if i - size >= 0 else 0)
    min_sum_of_submatrix = min_submatrix_sums[i][j] - (min_submatrix_sums[i - size][j] if i - size >= 0 else 0)
    return sum_of_submatrix - min_sum_of_submatrix <= K

count_good_submatrices = 0

# Перебираем все ячейки и проверяем возможность увеличения размера подматрицы
for i in range(N):
    for j in range(M):
        size = 1
        while can_increase_size(i, j, size):
            count_good_submatrices += 1
            size += 1

print(count_good_submatrices)

Этот код сначала считывает входные данные, затем заполняет дополнительные массивы сумм и минимальных сумм, а затем перебирает все ячейки матрицы, проверяя, можно ли увеличить размер подматрицы, заканчивающейся в этой ячейке. Если можно, то увеличивается количество хороших подматриц. В конце программа выводит результат.