QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353041 | #106. Bomb | jasper166 | 100 ✓ | 370ms | 77252kb | C++17 | 4.8kb | 2024-03-13 20:04:30 | 2024-03-13 20:04:31 |
Judging History
answer
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
const int N = 2505;
int a[N][N], lt[N][N], rt[N][N];
int w[N];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#ifdef JASPER
freopen("in1", "r", stdin);
#endif
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
char x; cin >> x;
a[i][j] = x - '0';
}
}
// for (int i = 1; i <= n; ++i)
// for (int j = 1; j <= m; ++j)
// cout << a[i][j] << " \n"[j == m];
//sub1: shortest consecutive 1ss
if (n == 1 || m == 1) {
if (n == 1) {
int ans = 1e9;
for (int i = 1; i <= m; ++i) {
if (a[1][i] == 0) continue;
int cur = 0;
while (i <= m && a[1][i]) {
++cur;
++i;
}
ans = min(ans, cur);
}
cout << ans << "\n";
return 0;
}
if (m == 1) {
int ans = 1e9;
for (int i = 1; i <= n; ++i) {
if (a[i][1] == 0) continue;
int cur = 0;
while (i <= n && a[i][1]) {
++cur;
++i;
}
ans = min(ans, cur);
}
cout << ans << "\n";
return 0;
}
}
if (n <= 100 && m <= 100) {
vector <vector <int>> prf(n + 5, vector <int> (m + 5, 0));
int earth = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
earth += (a[i][j] == 0);
prf[i][j] = prf[i][j - 1] + prf[i - 1][j] - prf[i - 1][j - 1] + a[i][j];
}
}
int ans = 0;
for (int x = 1; x <= n; ++x) {
for (int y = 1; y <= m; ++y) {
if (x * y <= ans) continue;
// prf(l)++, prf(r + 1)--;
vector <vector <int>> dmg(n + 2, vector <int> (m + 2, 0));
for (int i = 1; i + x - 1 <= n; ++i) {
for (int j = 1; j + y - 1 <= m; ++j) {
int I = i + x - 1, J = j + y - 1;
if (prf[I][J] + prf[i - 1][j - 1] - prf[I][j - 1] - prf[i - 1][J] == x * y) {
dmg[i][j] += 1;
dmg[I + 1][j] -= 1;
dmg[i][J + 1] -= 1;
dmg[I + 1][J + 1] += 1;
}
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
dmg[i][j] += dmg[i - 1][j] + dmg[i][j - 1] - dmg[i - 1][j - 1];
bool valid = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] && !dmg[i][j])
valid = 0;
}
}
if (valid) ans = max(ans, x * y);
}
}
cout << ans << "\n";
return 0;
}
for (int i = 1; i <= n; ++i) w[i] = m;
// two pointer to optimize
int min_h = 1e9;// minimum vertical strip of 1s;
for (int _i = 0; _i <= 1; _i++) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
lt[i][j] = a[i][j]? (lt[i][j - 1] + 1) : 0;
for (int j = m; j >= 1; --j)
rt[i][j] = a[i][j]? (rt[i][j + 1] + 1) : 0;
for (int j = 1; j <= m; ++j)
if (a[i][j]) w[1] = min(w[1], rt[i][j] + lt[i][j] - 1);
}
// find feasible height
for (int j = 1; j <= m; ++j) {
int k = 0; // length of consecutive 1s of current column
int l = 1e9, r = 1e9;
for (int i = 1; i <= n; ++i) {
if (a[i][j]) {
++k;
l = min(l, lt[i][j]);
r = min(r, rt[i][j]);
w[k] = min(w[k], r + l - 1);
}
else {
if (k) min_h = min(min_h, k);
l = r = 1e9;
k = 0;
}
}
}
for (int i = 1; i <= n / 2; ++i) {
for (int j = 1; j <= m; ++j)
swap(a[i][j], a[n - i + 1][j]);
}
}
int ans = 0;
for (int h = 1; h <= min(min_h, n); ++h) {
ans = max(ans, w[h] * h);
w[h + 1] = min(w[h + 1], w[h]); // width is bounded by the minimum horizontal strip
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 1
Accepted
time: 0ms
memory: 3800kb
input:
1 20 00001111101110011110
output:
3
result:
ok single line: '3'
Test #2:
score: 1
Accepted
time: 0ms
memory: 3692kb
input:
20 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0
output:
2
result:
ok single line: '2'
Test #3:
score: 1
Accepted
time: 0ms
memory: 13540kb
input:
2499 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
38
result:
ok single line: '38'
Test #4:
score: 1
Accepted
time: 0ms
memory: 13844kb
input:
2499 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
55
result:
ok single line: '55'
Test #5:
score: 1
Accepted
time: 0ms
memory: 3568kb
input:
1 2500 11111111111011111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
7
result:
ok single line: '7'
Test #6:
score: 1
Accepted
time: 0ms
memory: 3608kb
input:
1 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
33
result:
ok single line: '33'
Test #7:
score: 1
Accepted
time: 0ms
memory: 3556kb
input:
5 5 11111 11111 11011 11111 11111
output:
4
result:
ok single line: '4'
Test #8:
score: 1
Accepted
time: 1ms
memory: 3880kb
input:
20 20 11111000000000000000 11111000000000000000 11111100000000000000 11111111111000000000 00000111111000000000 00000111111000000000 00000011111000000000 00000001111100000000 00000000111110000000 00000000111110000000 00000000111110000000 00000000111110000000 00000000000000000000 00000000000000000000 ...
output:
8
result:
ok single line: '8'
Test #9:
score: 1
Accepted
time: 1ms
memory: 3936kb
input:
20 20 11111100000000000000 11111100000000000000 11111110000000000000 11111111111110000000 11111111111110000000 00000011111110000000 00000011111110000000 00000001111110000000 00000000011111100000 00000000001111110000 00000000001111110000 00000000001111110000 00000000001111110000 00000000001111110000 ...
output:
12
result:
ok single line: '12'
Test #10:
score: 1
Accepted
time: 0ms
memory: 3668kb
input:
14 13 0000011100000 0000011100000 0000011100000 0000011110000 0000000111000 0000000111000 0000001111000 0000011111000 0000111000000 0001111000000 0011111000000 0111111000000 1110000000000 1110000000000
output:
4
result:
ok single line: '4'
Test #11:
score: 1
Accepted
time: 1ms
memory: 3732kb
input:
20 19 1111110000000000000 1111111000000000000 1111111000000000000 1111111000000000000 1111111000000000000 1111111111111000000 0000001111111000000 0000000111111000000 0000000111111000000 0000000111111000000 0000000111111000000 0000000011111100000 0000000001111110000 0000000001111110000 00000000011111...
output:
10
result:
ok single line: '10'
Test #12:
score: 1
Accepted
time: 1ms
memory: 3624kb
input:
15 15 110000000000000 110000000000000 110000000000000 111000000000000 001100000000000 001100000000000 001110000000000 001111000000000 000001100000000 000001110000000 000001111000000 000001111100000 000000000110000 000000000110000 000000000110000
output:
2
result:
ok single line: '2'
Test #13:
score: 1
Accepted
time: 0ms
memory: 3576kb
input:
15 11 00111000000 00111000000 00111000000 00111000000 01111000000 11100000000 11100000000 11100000000 11110000000 11111000000 00011100000 00011100000 00011110000 00011111000 00011111100
output:
3
result:
ok single line: '3'
Test #14:
score: 1
Accepted
time: 1ms
memory: 3708kb
input:
16 16 0000111100001111 0000111100001111 0000111100001111 0000111100001111 1111000011110000 1111000011110000 1111000011110000 1111000011110000 0000111100001111 0000111100001111 0000111100001111 0000111100001111 1111000011110000 1111000011110000 1111000011110000 1111000011110000
output:
16
result:
ok single line: '16'
Test #15:
score: 1
Accepted
time: 0ms
memory: 3636kb
input:
18 18 111110000000000000 111110000000000000 111110000000000000 111111000000000000 111111111110000000 000001111110000000 000001111110000000 000001111110000000 000000111110000000 000000011111000000 000000001111100000 000000001111100000 000000001111100000 000000001111100000 000000001111100000 000000000...
output:
8
result:
ok single line: '8'
Test #16:
score: 1
Accepted
time: 1ms
memory: 3668kb
input:
20 20 11111111111111011111 11111111111111011111 11111111111111011111 11111111111111111111 11111111111111111111 00001111111111111111 11111111111111111111 11111111111111111111 11111111111111111111 11111111111110000000 11111111111111111111 11111111111111111111 11111111111111111111 11111111111111111111 ...
output:
20
result:
ok single line: '20'
Test #17:
score: 1
Accepted
time: 38ms
memory: 3864kb
input:
65 70 0000000000000000111110000000000000000000000000000000000000000000000000 0000000000000000111110000000000000000000000000000000000000000000000000 0000000000000000111110000000000000000011111000000000000000000000000000 0000000000000000111110000000000000000011111000000000011111000000000000 0001111111...
output:
15
result:
ok single line: '15'
Test #18:
score: 1
Accepted
time: 36ms
memory: 3900kb
input:
70 62 11110000000000000000000000000000000000000000000000000000000000 11110000000000000000000000000000000000000000000000000000000000 11110000000000000000000000000000000000000000000000000000000000 11110000000000000000000000000000000000000000000000000000000000 111100000000000000000000000000000000000000...
output:
6
result:
ok single line: '6'
Test #19:
score: 1
Accepted
time: 94ms
memory: 4048kb
input:
94 78 111111111111111100000000000000000000000000000000000000000000000000000000000000 111111111111111100000000000000000000000000000000000000000000000000000000000000 111111111111111100000000000000000000000000000000000000000000000000000000000000 111111111111111100000000000000000000000000000000000000000...
output:
22
result:
ok single line: '22'
Test #20:
score: 1
Accepted
time: 105ms
memory: 4240kb
input:
92 84 111111111111111110000000000000000000000000000000000000000000000000000000000000000000 111111111111111110000000000000000000000000000000000000000000000000000000000000000000 111111111111111110000000000000000000000000000000000000000000000000000000000000000000 111111111111111110000000000000000000000...
output:
27
result:
ok single line: '27'
Test #21:
score: 1
Accepted
time: 36ms
memory: 3880kb
input:
53 89 00000111100000000000000000000000000000000000000000000000000000000000000000000000000000000 00000111100000000000000000000000000000000000000000000000000000000000000000000000000000000 00000111100000000000000000000000000000000000000000000000000000000000000000000000000000000 000001111100000000000000...
output:
6
result:
ok single line: '6'
Test #22:
score: 1
Accepted
time: 88ms
memory: 3996kb
input:
76 93 000011111100000000000000000000000000000000000000000000000000000000000000000000000000000000000 000011111100000000000000000000000000000000000000000000000000000000000000000000000000000000000 000011111100000000000000000000000000000000000000000000000000000000000000000000000000000000000 000011111100...
output:
12
result:
ok single line: '12'
Test #23:
score: 1
Accepted
time: 158ms
memory: 4380kb
input:
100 100 1111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000 1111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000...
output:
209
result:
ok single line: '209'
Test #24:
score: 1
Accepted
time: 61ms
memory: 4008kb
input:
81 74 11111111111111111000000000000000000000000000000000000000000000000000000000 11111111111111111000000000000000000000000000000000000000000000000000000000 11111111111111111000000000000000000000000000000000000000000000000000000000 111111111111111110000000000000000000000000000000000000000000000000000...
output:
30
result:
ok single line: '30'
Test #25:
score: 1
Accepted
time: 172ms
memory: 4076kb
input:
100 100 1111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000 1111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000 111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000...
output:
80
result:
ok single line: '80'
Test #26:
score: 1
Accepted
time: 181ms
memory: 4092kb
input:
100 100 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
132
result:
ok single line: '132'
Test #27:
score: 1
Accepted
time: 0ms
memory: 8088kb
input:
295 268 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 11111111111111111111111...
output:
3
result:
ok single line: '3'
Test #28:
score: 1
Accepted
time: 4ms
memory: 8392kb
input:
290 383 1111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
20
result:
ok single line: '20'
Test #29:
score: 1
Accepted
time: 6ms
memory: 9744kb
input:
390 320 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000...
output:
3038
result:
ok single line: '3038'
Test #30:
score: 1
Accepted
time: 6ms
memory: 11168kb
input:
432 434 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
221
result:
ok single line: '221'
Test #31:
score: 1
Accepted
time: 0ms
memory: 9400kb
input:
334 450 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
391
result:
ok single line: '391'
Test #32:
score: 1
Accepted
time: 6ms
memory: 10552kb
input:
407 383 1111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
156
result:
ok single line: '156'
Test #33:
score: 1
Accepted
time: 3ms
memory: 11320kb
input:
450 450 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1235
result:
ok single line: '1235'
Test #34:
score: 1
Accepted
time: 0ms
memory: 8788kb
input:
356 231 000000000001111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000001111111111110000000000000000000000000000000000000...
output:
42
result:
ok single line: '42'
Test #35:
score: 1
Accepted
time: 0ms
memory: 11312kb
input:
450 450 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
192
result:
ok single line: '192'
Test #36:
score: 1
Accepted
time: 6ms
memory: 11344kb
input:
450 450 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1404
result:
ok single line: '1404'
Test #37:
score: 1
Accepted
time: 1ms
memory: 3704kb
input:
20 20 00000000001111111111 00000000001111111111 00000000001111111111 00000000001111111111 00000000011111111111 00000000011111111111 00000000011111111111 00000011111111111111 00011111111111111111 00011111110000000000 11111111100000000000 11111111100000000000 11111111100000000000 11111111100000000000 ...
output:
14
result:
ok single line: '14'
Test #38:
score: 1
Accepted
time: 370ms
memory: 77200kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
6250000
result:
ok single line: '6250000'
Test #39:
score: 1
Accepted
time: 1ms
memory: 3628kb
input:
20 20 00000000001111111111 00000000001111111111 00000000111111111111 00000001111111111111 00000001111111111111 00000001111111111111 00000001111111111111 00111111111111111111 00111111111111111111 00111111110000000000 11111111100000000000 11111111100000000000 11111111100000000000 11111111100000000000 ...
output:
24
result:
ok single line: '24'
Test #40:
score: 1
Accepted
time: 39ms
memory: 23312kb
input:
875 882 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
69552
result:
ok single line: '69552'
Test #41:
score: 1
Accepted
time: 1ms
memory: 3624kb
input:
20 20 00000000111111111111 00000011111111111111 00000011111111111111 00000111111111111111 00000111111111111111 00000111111111111111 00000111111111111111 00011111111111111111 00011111111111111111 11111111110000000000 11111111100000000000 11111111100000000000 11111111100000000000 11111111100000000000 ...
output:
36
result:
ok single line: '36'
Test #42:
score: 1
Accepted
time: 146ms
memory: 4076kb
input:
100 100 0000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111 0000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111 000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111...
output:
651
result:
ok single line: '651'
Test #43:
score: 1
Accepted
time: 270ms
memory: 77012kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
250500
result:
ok single line: '250500'
Test #44:
score: 1
Accepted
time: 8ms
memory: 11268kb
input:
450 450 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111...
output:
12864
result:
ok single line: '12864'
Test #45:
score: 1
Accepted
time: 288ms
memory: 77200kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
399456
result:
ok single line: '399456'
Test #46:
score: 1
Accepted
time: 229ms
memory: 77028kb
input:
2500 2500 11111111111111111111111110000000000000000000000000111111111111111111111111100000000000000000000000001111111111111111111111111000000000000000000000000011111111111111111111111110000000000000000000000000111111111111111111111111100000000000000000000000001111111111111111111111111000000000000000...
output:
625
result:
ok single line: '625'
Test #47:
score: 1
Accepted
time: 287ms
memory: 77204kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
395486
result:
ok single line: '395486'
Test #48:
score: 1
Accepted
time: 264ms
memory: 77020kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
3360
result:
ok single line: '3360'
Test #49:
score: 1
Accepted
time: 351ms
memory: 77008kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
28
result:
ok single line: '28'
Test #50:
score: 1
Accepted
time: 271ms
memory: 77008kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111...
output:
7348
result:
ok single line: '7348'
Test #51:
score: 1
Accepted
time: 269ms
memory: 77020kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
6622
result:
ok single line: '6622'
Test #52:
score: 1
Accepted
time: 274ms
memory: 77180kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
5593
result:
ok single line: '5593'
Test #53:
score: 1
Accepted
time: 258ms
memory: 77236kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
4545
result:
ok single line: '4545'
Test #54:
score: 1
Accepted
time: 201ms
memory: 77252kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
4067
result:
ok single line: '4067'
Test #55:
score: 1
Accepted
time: 206ms
memory: 76960kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2806
result:
ok single line: '2806'
Test #56:
score: 1
Accepted
time: 347ms
memory: 76964kb
input:
2500 2500 11111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111...
output:
122500
result:
ok single line: '122500'
Test #57:
score: 1
Accepted
time: 218ms
memory: 76884kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
4674
result:
ok single line: '4674'
Test #58:
score: 1
Accepted
time: 201ms
memory: 77024kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
6272
result:
ok single line: '6272'
Test #59:
score: 1
Accepted
time: 186ms
memory: 77032kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
3337
result:
ok single line: '3337'
Test #60:
score: 1
Accepted
time: 255ms
memory: 76988kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
870
result:
ok single line: '870'
Test #61:
score: 1
Accepted
time: 358ms
memory: 77032kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
532
result:
ok single line: '532'
Test #62:
score: 1
Accepted
time: 368ms
memory: 76960kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
114271
result:
ok single line: '114271'
Test #63:
score: 1
Accepted
time: 363ms
memory: 77232kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1560001
result:
ok single line: '1560001'
Test #64:
score: 1
Accepted
time: 188ms
memory: 77012kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
62500
result:
ok single line: '62500'
Test #65:
score: 1
Accepted
time: 239ms
memory: 76988kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1400
result:
ok single line: '1400'
Test #66:
score: 1
Accepted
time: 281ms
memory: 77200kb
input:
2500 2500 00000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
9910
result:
ok single line: '9910'
Test #67:
score: 1
Accepted
time: 259ms
memory: 76964kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
9879
result:
ok single line: '9879'
Test #68:
score: 1
Accepted
time: 304ms
memory: 77072kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
16224
result:
ok single line: '16224'
Test #69:
score: 1
Accepted
time: 201ms
memory: 76912kb
input:
2500 2500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
6300
result:
ok single line: '6300'
Test #70:
score: 1
Accepted
time: 92ms
memory: 62332kb
input:
2000 2000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
59760
result:
ok single line: '59760'
Test #71:
score: 1
Accepted
time: 182ms
memory: 77196kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
40480
result:
ok single line: '40480'
Test #72:
score: 1
Accepted
time: 194ms
memory: 76960kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
137159
result:
ok single line: '137159'
Test #73:
score: 1
Accepted
time: 200ms
memory: 76956kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
32110
result:
ok single line: '32110'
Test #74:
score: 1
Accepted
time: 195ms
memory: 76968kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
10914
result:
ok single line: '10914'
Test #75:
score: 1
Accepted
time: 202ms
memory: 76960kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
124074
result:
ok single line: '124074'
Test #76:
score: 1
Accepted
time: 214ms
memory: 77236kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4617
result:
ok single line: '4617'
Test #77:
score: 1
Accepted
time: 211ms
memory: 76944kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
106981
result:
ok single line: '106981'
Test #78:
score: 1
Accepted
time: 203ms
memory: 77016kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
44980
result:
ok single line: '44980'
Test #79:
score: 1
Accepted
time: 114ms
memory: 76960kb
input:
2500 2500 11111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1365
result:
ok single line: '1365'
Test #80:
score: 1
Accepted
time: 133ms
memory: 76960kb
input:
2500 2500 11111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
602
result:
ok single line: '602'
Test #81:
score: 1
Accepted
time: 134ms
memory: 76960kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000...
output:
2709
result:
ok single line: '2709'
Test #82:
score: 1
Accepted
time: 202ms
memory: 77180kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
149556
result:
ok single line: '149556'
Test #83:
score: 1
Accepted
time: 198ms
memory: 77200kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
11289
result:
ok single line: '11289'
Test #84:
score: 1
Accepted
time: 132ms
memory: 76988kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000...
output:
366
result:
ok single line: '366'
Test #85:
score: 1
Accepted
time: 200ms
memory: 76960kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4814
result:
ok single line: '4814'
Test #86:
score: 1
Accepted
time: 338ms
memory: 77020kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
132
result:
ok single line: '132'
Test #87:
score: 1
Accepted
time: 189ms
memory: 77004kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
589
result:
ok single line: '589'
Test #88:
score: 1
Accepted
time: 196ms
memory: 77020kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
56448
result:
ok single line: '56448'
Test #89:
score: 1
Accepted
time: 227ms
memory: 76944kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
10044
result:
ok single line: '10044'
Test #90:
score: 1
Accepted
time: 114ms
memory: 62556kb
input:
2000 2000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
6384
result:
ok single line: '6384'
Test #91:
score: 1
Accepted
time: 215ms
memory: 76884kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
15330
result:
ok single line: '15330'
Test #92:
score: 1
Accepted
time: 253ms
memory: 76980kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
47759
result:
ok single line: '47759'
Test #93:
score: 1
Accepted
time: 336ms
memory: 77236kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
624
result:
ok single line: '624'
Test #94:
score: 1
Accepted
time: 251ms
memory: 77020kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
16695
result:
ok single line: '16695'
Test #95:
score: 1
Accepted
time: 206ms
memory: 77200kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
19224
result:
ok single line: '19224'
Test #96:
score: 1
Accepted
time: 229ms
memory: 76964kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
89386
result:
ok single line: '89386'
Test #97:
score: 1
Accepted
time: 324ms
memory: 76980kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
243
result:
ok single line: '243'
Test #98:
score: 1
Accepted
time: 208ms
memory: 77248kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
73840
result:
ok single line: '73840'
Test #99:
score: 1
Accepted
time: 227ms
memory: 77020kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
10764
result:
ok single line: '10764'
Test #100:
score: 1
Accepted
time: 314ms
memory: 77232kb
input:
2500 2500 11111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
135
result:
ok single line: '135'