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

Задача A. Кесте

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

1 second

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

256 megabytes

Сізге бүтін оң сандардан тұратын $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();
}
}