Largest Square Submatrix of all 1's

Find the largest square submatrix consisting entirely of 1s as fast as possible.

Input

A 10,000 x 10,000 matrix of uint8 values (0 or 1) on STDIN.

0, 1, 0, 1, 1
0, 1, 1, 1, 1
0, 0, 1, 0, 0
1, 0, 1, 1, 0

Output

Print the side length of the largest all-ones square submatrix to STDOUT. The answer is guaranteed to be greater than 1.

For the example above, the output is:

Restrictions:60s256Mb 1 Score Packages

Feel free to create an issue if you need an extra library from the standard Ubuntu repository.

Name	Version	Description
libc6-dev	2.39-0ubuntu8.7	GNU C Library: Development Libraries and Header Files Contains the symlinks, headers, and object files needed to compile and link programs which use the standard C library.
libclang-common-14-dev	1:14.0.6-19build4	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-15-dev	1:15.0.7-14build3	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-16-dev	1:16.0.6-23ubuntu4	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-17-dev	1:17.0.6-9ubuntu1	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-18-dev	1:18.1.3-1ubuntu1	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-19-dev	1:19.1.1-1ubuntu1~24.04.2	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-20-dev	1:20.1.2-0ubuntu1~24.04.3	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libcrypt-dev	1:4.4.36-4build1	libcrypt development files This package contains the files needed for developing applications that use libcrypt.
libgcc-10-dev	10.5.0-4ubuntu2.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-11-dev	11.5.0-1ubuntu1~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-12-dev	12.4.0-2ubuntu1~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-13-dev	13.3.0-6ubuntu2~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-14-dev	14.2.0-4ubuntu2~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libobjc-13-dev	13.3.0-6ubuntu2~24.04.1	Runtime library for GNU Objective-C applications (development files) This package contains the headers and static library files needed to build GNU ObjC applications.
libssl-dev	3.0.13-0ubuntu3.11	Secure Sockets Layer toolkit - development files This package is part of the OpenSSL project's implementation of the SSL and TLS cryptographic protocols for secure communication over the Internet. . It contains development libraries, header files, and manpages for libssl and libcrypto.
libstdc++-10-dev	10.5.0-4ubuntu2.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-11-dev	11.5.0-1ubuntu1~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-12-dev	12.4.0-2ubuntu1~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-13-dev	13.3.0-6ubuntu2~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-14-dev	14.2.0-4ubuntu2~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libtbb-dev	2021.11.0-2ubuntu2	parallelism library for C++ - development files TBB is a library that helps you leverage multi-core processor performance without having to be a threading expert. It represents a higher-level, task-based parallelism that abstracts platform details and threading mechanism for performance and scalability. . (Note: if you are a user of the i386 architecture, i.e., 32-bit Intel or compatible hardware, this package only supports Pentium4-compatible and higher processors.) . This package includes the TBB development files.

#	Author	Score	Language	Solution
1	Andrew Epstein Master	1,860	CPP g++14.2.0	Sep 13, 2026 19:24 9,798,589 ns · 744,000 ns · 0 ns · 20,480 B
2	Tomislav Tunkovic Grandmaster	1,887	CPP g++14.2.0	Aug 15, 2026 11:10 8,705,239 ns · 755,000 ns · 0 ns · 20,480 B
3	Victor Mercklé Grandmaster	1,927	CPP g++14.2.0	Sep 5, 2026 16:35 9,601,050 ns · 771,000 ns · 0 ns · 20,480 B
4	marko1597 Expert	2,605	CPP clang++19.1.1	Aug 17, 2026 08:19 9,152,735 ns · 1,042,000 ns · 0 ns · 2,117,632 B
5	olliecrow Expert	4,875	CPP clang++18.1.3	Apr 21, 2026 21:37 16,785,856 ns · 0 ns · 1,950,000 ns · 2,457,600 B
6	Yuriy Lyfenko Expert	8,563	CPP g++13.3.0	Nov 19, 2025 19:05 22,056,658 ns · 3,425,000 ns · 0 ns · 2,531,328 B
7	M-Rochat Expert	11,342	CPP g++13.3.0	May 22, 2026 12:27 15,008,909 ns · 3,481,000 ns · 1,056,000 ns · 2,121,728 B
8	Sergey Serebryakov Skilled	21,588	CPP g++13.3.0	Mar 5, 2026 22:44 29,011,831 ns · 7,556,000 ns · 1,079,000 ns · 2,277,376 B
9	Yehor Bondar Skilled	24,240	CPP clang++18.1.3	Aug 13, 2026 12:57 19,756,553 ns · 8,527,000 ns · 1,169,000 ns · 2,113,536 B
10	Josu San Martin Expert	25,585	CPP clang++20.1.2	Aug 30, 2026 19:07 18,598,189 ns · 10,234,000 ns · 0 ns · 2,117,632 B
11	Dominique Garmier Expert	26,142	CPP clang++18.1.3	May 1, 2026 08:44 27,719,335 ns · 9,412,000 ns · 1,045,000 ns · 2,367,488 B
12	Mukundan Novice	33,143	CPP g++13.3.0	Mar 4, 2026 11:44 42,282,848 ns · 12,238,000 ns · 1,019,000 ns · 2,387,968 B
13	zielaj Skilled	36,498	CPP g++13.3.0	May 27, 2025 02:11 29,845,100 ns · 14,599,000 ns · 0 ns · 2,531,328 B
14	Charles Cabergs Skilled	58,282	CPP g++13.3.0	Apr 30, 2026 06:47 45,379,688 ns · 12,163,000 ns · 11,150,000 ns · 2,310,144 B
15	apuxbt Skilled	74,157	CPP g++10.5.0	Sep 16, 2026 09:13 39,821,319 ns · 21,904,000 ns · 7,759,000 ns · 2,113,536 B
16	limanjun99 Expert	79,395	CPP g++14.2.0	Apr 24, 2026 10:21 46,639,351 ns · 30,734,000 ns · 1,024,000 ns · 2,523,136 B
17	Keefe Expert	82,190	CPP g++13.3.0	May 26, 2025 18:42 60,834,324 ns · 30,884,000 ns · 1,992,000 ns · 2,498,560 B
18	TudyM Skilled	96,597	CPP clang++20.1.2	Apr 26, 2026 21:26 58,989,817 ns · 32,538,000 ns · 6,101,000 ns · 2,310,144 B
19	Warren Fu Apprentice	98,257	CPP clang++20.1.2	Aug 1, 2026 04:57 50,100,556 ns · 27,316,000 ns · 11,987,000 ns · 2,121,728 B
20	mgilder Apprentice	98,910	RUST rust-1.95.0	Sep 2, 2026 03:17 49,512,838 ns · 32,004,000 ns · 7,560,000 ns · 2,117,632 B
21	Andrew Tsibin Expert	101,540	RUST rust-1.95.0	Jul 16, 2026 09:55 50,205,900 ns · 28,333,000 ns · 12,283,000 ns · 2,113,536 B
22	Haha Expert Expert	243,368	CPP clang++18.1.3	May 14, 2025 17:52 117,659,234 ns · 55,197,000 ns · 42,150,000 ns · 2,379,776 B
23	idatsy Novice	287,535	RUST rust-1.92.0	Dec 20, 2025 21:47 140,057,149 ns · 106,013,000 ns · 9,001,000 ns · 2,453,504 B
24	ethereal Skilled	308,903	GO go1.24.3	May 25, 2025 01:33 149,406,653 ns · 122,557,000 ns · 1,004,000 ns · 2,338,816 B
25	A_Shaman Skilled	350,037	CPP g++10.5.0	Jul 2, 2026 12:39 149,331,625 ns · 138,987,000 ns · 1,028,000 ns · 2,113,536 B
26	Aleksei Shahoika Skilled	443,125	CPP g++10.5.0	May 9, 2026 16:16 195,448,008 ns · 176,193,000 ns · 1,057,000 ns · 2,510,848 B
27	Arnav Aggarwal Apprentice	462,050	CPP g++13.3.0	May 19, 2025 06:13 212,422,415 ns · 172,832,000 ns · 11,988,000 ns · 2,539,520 B
28	Sergey Stremin Skilled	553,025	RUST rust-1.87.0	May 23, 2025 14:02 244,253,047 ns · 220,210,000 ns · 1,000,000 ns · 2,285,568 B
29	Mikhail Shirokov Skilled	616,110	CPP g++13.3.0	Jun 3, 2025 12:55 267,303,550 ns · 246,444,000 ns · 0 ns · 2,273,280 B
30	E Sequeira Skilled	645,587	CPP g++10.5.0	May 9, 2026 14:20 273,172,011 ns · 257,228,000 ns · 1,007,000 ns · 2,314,240 B
31	vahook Skilled	706,128	CPP g++13.3.0	May 31, 2025 19:25 304,303,093 ns · 280,455,000 ns · 1,996,000 ns · 2,404,352 B
32	Ben Skilled	754,710	CPP g++13.3.0	Apr 20, 2026 16:46 331,741,354 ns · 299,885,000 ns · 1,999,000 ns · 2,306,048 B
33	Aniruddha Deb Expert	856,275	CPP g++13.3.0	Jul 27, 2025 21:40 367,588,201 ns · 342,510,000 ns · 0 ns · 2,424,832 B
34	Iheb Apprentice	872,210	CPP g++13.3.0	Jun 6, 2025 09:39 370,544,670 ns · 346,885,000 ns · 1,999,000 ns · 2,285,568 B
35	Ahamed Novice	938,103	CPP g++13.3.0	Sep 18, 2025 17:06 398,387,070 ns · 375,241,000 ns · 0 ns · 2,277,376 B
36	Andrey Nikolaev Novice	1,042,408	RUST rust-1.89.0	Aug 18, 2025 06:31 439,982,260 ns · 371,967,000 ns · 44,996,000 ns · 2,342,912 B
37	Franek Korta Skilled	1,120,828	CPP g++13.3.0	Jun 12, 2025 21:53 475,106,050 ns · 448,331,000 ns · 0 ns · 2,269,184 B
38	Taylor Dettling Skilled	1,263,105	RUST rust-1.95.0	Apr 21, 2026 01:30 556,701,118 ns · 377,434,000 ns · 127,808,000 ns · 2,502,656 B
39	izotoff Skilled	1,289,568	GO go1.25.4	Nov 20, 2025 20:31 542,228,642 ns · 513,824,000 ns · 2,003,000 ns · 2,326,528 B
40	Genos0 Novice	1,306,765	CPP g++10.5.0	Jul 10, 2026 18:39 556,777,916 ns · 398,645,000 ns · 124,061,000 ns · 61,440 B
41	Tony Skilled	1,309,330	CPP g++10.5.0	Aug 1, 2026 22:07 561,714,793 ns · 399,872,000 ns · 123,860,000 ns · 77,824 B
42	Roshan Novice	1,313,400	RUST rust-1.92.0	Jan 2, 2026 15:29 557,258,828 ns · 479,329,000 ns · 46,031,000 ns · 2,424,832 B
43	Andrii Stolitnii Novice	1,315,147	CPP g++10.5.0	May 10, 2026 00:10 566,083,917 ns · 398,249,000 ns · 127,810,000 ns · 438,272 B
44	Osnaga Octavian-Alexandru Novice	1,332,375	CPP g++10.5.0	Jun 26, 2026 15:44 556,485,107 ns · 401,545,000 ns · 131,405,000 ns · 61,440 B
45	satoru.net Novice	1,541,553	CSHARP 9.0.13	Feb 23, 2026 18:27 638,510,887 ns · 571,649,000 ns · 44,972,000 ns · 2,482,176 B
46	Oleg Kovalov Skilled	1,648,385	GO go1.26.2	Jul 16, 2026 20:58 688,971,017 ns · 531,271,000 ns · 128,083,000 ns · 90,112 B
47	Hayden Donnelly Apprentice	5,670,513	CPP g++13.3.0	Jun 2, 2025 01:25 2,294,825,938 ns · 2,268,205,000 ns · 0 ns · 2,433,024 B
48	AnSa Skilled	6,019,898	CPP g++13.3.0	Dec 22, 2025 08:25 2,436,950,289 ns · 2,405,960,000 ns · 1,999,000 ns · 2,260,992 B
49	Chandrasekaran Akash Skilled	8,999,638	CPP g++13.3.0	May 19, 2025 17:08 3,629,007,043 ns · 3,540,891,000 ns · 58,964,000 ns · 2,482,176 B
50	Martin Stensgård Skilled	9,113,388	CPP g++13.3.0	Oct 3, 2025 18:07 3,671,236,064 ns · 3,600,376,000 ns · 44,979,000 ns · 2,379,776 B
51	MikhailBurdukov Novice	9,397,330	CPP clang++18.1.3	Nov 9, 2025 20:46 3,793,581,340 ns · 3,714,957,000 ns · 43,975,000 ns · 2,277,376 B

Model	Intel(R) Xeon(R) CPU E3-1271 v3 @ 3.60GHz
Cores	1