3-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача A. Матрицы

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вам дана матрица размера $N \times M$, состоящая из целых положительных чисел, а также целое число $K$. Назовем подматрицу хорошей, если она является квадратом и сумма этой подматрицы не больше $K$. Посчитайте количество хороших подматриц. Подматрицей называется такая матрица, которую можно получить из исходной, если удалить из нее несколько(возможно ноль) столбцов с левого и правого края, а также несколько(возможно ноль) строк с верхнего и нижнего края. При этом подматрица не должна быть пустой.

Формат входного файла

В первой строке заданы $3$ целых числа $N$, $M$, $K$ — размеры матрицы и ограничение на сумму. ($1 <= N, M <= 1500$, $0 <= K <= 10^9$) В следующих $N$ строках содержится по $M$ целых положительных чисел — содержимое матрицы (числа по значению от $1$ до $1000$).

Формат выходного файла

Выведите одно число — количество подходящих подматриц.

Система оценки

Данная задача содержит $6$ подзадач, в которых выполняются следующие ограничения:

1. Тесты из условия. Оценивается в $0$ баллов.
2. $N, M <= 2$. Оценивается в $15$ баллов.
3. $N, M <= 100$. Оценивается в $17$ баллов.
4. $N, M <= 500$. Оценивается в $24$ балла.
5. $N, M <= 1500$ и матрица состоит только из единичек. Оценивается в $15$ баллов.
6. Исходные ограничения. Оценивается в $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

( Abay Baimukanov )

Комментарий/решение

показать/скрыть код

/*Nursayat*/
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,m,k;
	int l=0,x,v;
	cin>>n>>m>>k;
	int b[500][500];
	int c[500][500];
	for (int i=1; i<=n; i++){
		int s=0;
		for (int j=1; j<=m; j++){
			cin>>v;
			if (v<=k) l+=1;
			s+=v;
			b[i][j]=s;
		}
	}
	for (int i=1; i<=n; i++){
		int p=0;
		for (int j=1; j<=m; j++){
			p+=b[j][i];
			c[j][i]=p;
		}
	}
	int minn=min(n,m);
	int z=2;
	while (z<minn){
		for (int i=z; i<=n; i++){
			for (int j=z; j<=m; j++){
				x=(c[i][j]-c[i-z][j]-c[i][j-z])+c[i-z][j-z];
				if (x<=k) l+=1;
			}
		}
		z+=1;
	}

	cout<<endl<<l;
	
}

7 тест не правильный ответ

Полное решение

показать/скрыть код

#include<bits/stdc++.h>
#define ll            long long	
#define pb            push_back
#define F             first
#define S             second
#define mk            make_pair
#define skip          continue;
#define ld            long double
#define pf			  push_front
using namespace std;
const int L=1e7+11;
const int N=2e3;
const ll mod=1000000007;
const double pi=3.14159265359;
ll a[N][N];
ll pref[N][N];
void solve(){
	int n,m,k;
	cin>>n>>m>>k;
	ll ans=0;bool o=1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>a[i][j];
			pref[i][1]=a[i][1]+pref[i-1][1];
			pref[1][j]=a[1][j]+pref[1][j-1];
			if(a[i][j]>1)o=0;
		}
	}
	if(n>500 && m>500 && o){
		ll l=1,r=min(n,m),x=0;
		while(l<=r){
			ll m=(l+r)/2;
			if(m*m<=k){
				l=m+1;
				x=m;
			}else{
				r=m-1;
			}
		}
		ll ans=0;
		for(int i=1; i<=x; i++){
			ans+=(n-i+1)*(m-i+1);
		}
		cout<<ans<<endl;
		return;
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			pref[i][j]=pref[i-1][j]+pref[i][j-1]+a[i][j]-pref[i-1][j-1];
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			ll l=0,r=min(n-i,m-j),p=-1;
			while(l<=r){
				ll m=(l+r)/2;
				ll sum=pref[i+m][j+m]+pref[i-1][j-1]-pref[i-1][j+m]-pref[i+m][j-1];
				if(sum<=k){
					p=m;
					l=m+1;
				}else{
					r=m-1;
				}
			}
			ans+=p+1;	
		}
	}
	cout<<ans<<endl;
}
/*	
*/ 
int main(){	
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", " w", stdout);
int tt=1;
//cin>>tt;
while(tt--){
	solve();
}
}