提出 #76453456

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;

#define int long long 

const int N=500+5;

bool st;
int h,w,cnt,k;
int sum[N][N];
string s[N];
int temp[N*N];
bool ed;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cerr<<(double)(&st-&ed)/1024/1024<<'\n';
	cin>>h>>w>>k;
	for(int i=1;i<=h;i++) {
		cin>>s[i];
		for(int j=0;j<w;j++) sum[i][j+1]=sum[i][j]+sum[i-1][j+1]-sum[i-1][j]+s[i][j]-'0';
	}
	for(int i=1;i<=h;i++) {
		for(int j=i;j<=h;j++) {
			temp[0]++;
			for(int x=1;x<=w;x++) {
				if(sum[j][x]-sum[i-1][x]>=k) cnt+=temp[sum[j][x]-sum[i-1][x]-k];
				temp[sum[j][x]-sum[i-1][x]]++;
			}for(int x=1;x<=w;x++) temp[sum[j][x]-sum[i-1][x]]--;
			temp[0]--;
		}
	}cout<<cnt;
	return 0;
}

提出情報

提出日時
問題 D - Count Subgrid Sum = K
ユーザ wallacewan
言語 C++23 (GCC 15.2.0)
得点 425
コード長 750 Byte
結果 AC
実行時間 236 ms
メモリ 8136 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 425 / 425
結果
AC × 3
AC × 31
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 1 ms 3912 KiB
sample_02.txt AC 1 ms 4092 KiB
sample_03.txt AC 1 ms 3828 KiB
test_01.txt AC 1 ms 3832 KiB
test_02.txt AC 1 ms 3836 KiB
test_03.txt AC 1 ms 3860 KiB
test_04.txt AC 1 ms 3812 KiB
test_05.txt AC 236 ms 6008 KiB
test_06.txt AC 221 ms 6152 KiB
test_07.txt AC 117 ms 8136 KiB
test_08.txt AC 110 ms 7852 KiB
test_09.txt AC 203 ms 6128 KiB
test_10.txt AC 205 ms 6040 KiB
test_11.txt AC 206 ms 6008 KiB
test_12.txt AC 207 ms 5976 KiB
test_13.txt AC 127 ms 6068 KiB
test_14.txt AC 114 ms 6004 KiB
test_15.txt AC 150 ms 6128 KiB
test_16.txt AC 117 ms 5976 KiB
test_17.txt AC 81 ms 6004 KiB
test_18.txt AC 70 ms 6012 KiB
test_19.txt AC 89 ms 6008 KiB
test_20.txt AC 85 ms 6152 KiB
test_21.txt AC 124 ms 7024 KiB
test_22.txt AC 98 ms 7092 KiB
test_23.txt AC 82 ms 6252 KiB
test_24.txt AC 123 ms 6984 KiB
test_25.txt AC 229 ms 6004 KiB
test_26.txt AC 226 ms 6012 KiB
test_27.txt AC 219 ms 6268 KiB
test_28.txt AC 227 ms 6036 KiB