(cache)Submission #77418256 - AtCoder Beginner Contest 461

Contest Duration: 2026-06-06(Sat) 21:00 - 2026-06-06(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #77418256

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <inttypes.h>
int H, W, K;
char S[512][512];
int sum[512][512];
int main(void) {
  int i, j, k;
  uint64_t ans = 0;
  if (scanf("%d%d%d", &H, &W, &K) != 3) return 1;
  for (i = 1; i <= H; i++) {
    if (scanf("%510s", S[i] + 1) != 1) return 1;
    for (j = 1; j <= W; j++) {
      sum[i][j] = sum[i][j - 1] + (S[i][j] - '0');
    }
    for (j = 1; j <= W; j++) {
      sum[i][j] += sum[i - 1][j];
    }
  }
  for (i = 0; i < H; i++) {
    for (j = i + 1; j <= H; j++) {
      for (k = 0; k < W; k++) {
        int le = k, g = W + 1, l = k, ge = W + 1;
        while (le + 1 < g) {
          int m = le + (g - le) / 2;
          int meow = sum[j][m] - sum[i][m] - sum[j][k] + sum[i][k];
          if (meow > K) g = m; else le = m;
        }
        while (l + 1 < ge) {
          int m = l + (ge - l) / 2;
          int meow = sum[j][m] - sum[i][m] - sum[j][k] + sum[i][k];
          if (meow >= K) ge = m; else l = m;
        }
        ans += g - l - 1;
      }
    }
  }
  printf("%" PRIu64 "\n", ans);
  return 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

int H, W, K;
char S[512][512];

int sum[512][512];

int main(void) {
	int i, j, k;
	uint64_t ans = 0;
	if (scanf("%d%d%d", &H, &W, &K) != 3) return 1;
	for (i = 1; i <= H; i++) {
		if (scanf("%510s", S[i] + 1) != 1) return 1;
		for (j = 1; j <= W; j++) {
			sum[i][j] = sum[i][j - 1] + (S[i][j] - '0');
		}
		for (j = 1; j <= W; j++) {
			sum[i][j] += sum[i - 1][j];
		}
	}
	for (i = 0; i < H; i++) {
		for (j = i + 1; j <= H; j++) {
			for (k = 0; k < W; k++) {
				int le = k, g = W + 1, l = k, ge = W + 1;
				while (le + 1 < g) {
					int m = le + (g - le) / 2;
					int meow = sum[j][m] - sum[i][m] - sum[j][k] + sum[i][k];
					if (meow > K) g = m; else le = m;
				}
				while (l + 1 < ge) {
					int m = l + (ge - l) / 2;
					int meow = sum[j][m] - sum[i][m] - sum[j][k] + sum[i][k];
					if (meow >= K) ge = m; else l = m;
				}
				ans += g - l - 1;
			}
		}
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

Submission Info

Submission Time	2026-07-12 08:33:58
Task	D - Count Subgrid Sum = K
User	mikecat
Language	C23 (GCC 14.2.0)
Score	425
Code Size	1001 Byte
Status	AC
Exec Time	2169 ms
Memory	2956 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 3

× 31

Set Name	Test Cases
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

Case Name	Status	Exec Time	Memory
sample_01.txt	AC	1 ms	1644 KiB
sample_02.txt	AC	0 ms	1616 KiB
sample_03.txt	AC	1 ms	1696 KiB
test_01.txt	AC	0 ms	1592 KiB
test_02.txt	AC	0 ms	1568 KiB
test_03.txt	AC	1 ms	1644 KiB
test_04.txt	AC	0 ms	1592 KiB
test_05.txt	AC	952 ms	2852 KiB
test_06.txt	AC	1198 ms	2948 KiB
test_07.txt	AC	835 ms	2872 KiB
test_08.txt	AC	1199 ms	2852 KiB
test_09.txt	AC	1191 ms	2892 KiB
test_10.txt	AC	1268 ms	2948 KiB
test_11.txt	AC	1197 ms	2900 KiB
test_12.txt	AC	1458 ms	2892 KiB
test_13.txt	AC	1560 ms	2956 KiB
test_14.txt	AC	1190 ms	2896 KiB
test_15.txt	AC	1209 ms	2848 KiB
test_16.txt	AC	2076 ms	2924 KiB
test_17.txt	AC	2169 ms	2948 KiB
test_18.txt	AC	1200 ms	2884 KiB
test_19.txt	AC	1204 ms	2872 KiB
test_20.txt	AC	1986 ms	2872 KiB
test_21.txt	AC	1728 ms	2868 KiB
test_22.txt	AC	1198 ms	2948 KiB
test_23.txt	AC	1204 ms	2896 KiB
test_24.txt	AC	1209 ms	2884 KiB
test_25.txt	AC	1207 ms	2888 KiB
test_26.txt	AC	941 ms	2872 KiB
test_27.txt	AC	1184 ms	2848 KiB
test_28.txt	AC	930 ms	2956 KiB