QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#701578#85. Leverage MDTTheZoneAC ✓24ms26044kbC++202.5kb2024-11-02 14:23:212024-11-02 14:23:21

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 14:23:21]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:26044kb
  • [2024-11-02 14:23:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define ar array
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
const int N = 2001;
char a[N][N];
int n , m;
int G[N][N] , B[N][N];

bool f(int mid)
{
    for(int j = 0 ; j <= m - mid; j++)
    {
        int cnt = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            int good = G[i][mid + j] - G[i][j];
            int bad = B[i][mid + j] - B[i][j];
            if(good == mid || good == 0) ++cnt;
            else cnt = 0;
            if(cnt >= mid) return true;
        } 
    }
    return false;
}
 
void Solve()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            G[i][j] = G[i][j - 1];
            B[i][j] = B[i][j - 1];
            if(a[i][j] == 'G') G[i][j] = G[i][j - 1] + 1;
            else B[i][j] = B[i][j - 1] + 1;
        }
    }
    
    ll l = 1 , r = min(n , m) + 1;
    while(r - l > 1)
    {
        int mid = (l + r) / 2;
        if(f(mid)) l = mid;
        else r = mid;
    }
    cout << (l) * (l) << '\n';
}
 
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int truongdoan = 1;
    //cin >> truongdoan;
 
    while(truongdoan-->0)
    {
        Solve();
    }
 
    return 0; 
}

























































































































































































































































































































































































































详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5752kb

input:

2 2
GG
GG

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5660kb

input:

1 1
B

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5668kb

input:

2 2
BB
BB

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5752kb

input:

2 2
GB
BB

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5660kb

input:

2 2
BG
BB

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5668kb

input:

2 2
BB
GB

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5748kb

input:

2 2
BB
BG

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

2 2
BB
GG

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 1ms
memory: 5796kb

input:

2 2
BG
BG

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 1ms
memory: 5728kb

input:

2 2
BG
BG

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 1ms
memory: 5660kb

input:

2 2
GG
GG

output:

4

result:

ok single line: '4'

Test #12:

score: 0
Accepted
time: 0ms
memory: 5824kb

input:

5 5
GGGGG
GBBBG
GBBBG
GBBBG
GGGGG

output:

9

result:

ok single line: '9'

Test #13:

score: 0
Accepted
time: 1ms
memory: 5688kb

input:

5 1
G
G
G
G
G

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 1ms
memory: 5816kb

input:

5 1
G
B
G
G
G

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 1ms
memory: 5740kb

input:

1 5
GGGGG

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 0ms
memory: 5604kb

input:

1 5
GBGGG

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 1ms
memory: 5736kb

input:

10 10
GBBBBGBBGB
GBBBGGBBGB
BGBGBBGGBB
BGBGBBBGBG
BGBBGGBGBG
GGBGBBBGGG
BBGGBGBBBB
GGGGBGGGGG
GBBBBGBBGB
BGBBGGGGBB

output:

9

result:

ok single line: '9'

Test #18:

score: 0
Accepted
time: 0ms
memory: 5796kb

input:

10 10
GGBBGBGBGB
BGGBGGBGGB
BGGGBGBGGG
GGGBGBGGBB
BBBBBGBBGB
BGBBBGGGGB
BGBBGBGGGG
GBBGGGBBBB
GGBGBGBGGB
BBBBGBGBGG

output:

9

result:

ok single line: '9'

Test #19:

score: 0
Accepted
time: 0ms
memory: 5980kb

input:

30 30
BBGBGBGGGGGBBGBBGBGBBGGGGBBGGG
BBBBBBGBGGBGBGBBGBGGBBGBBBGBBG
BGBBBGGGGBGGBBGBGGGBBBBGGGGBBB
BBGBBGGBBBBBGGGGGBBBGBGGBGGBGG
BGBBBGGGGBBGGBBGBBGGBGGGBGGGGB
GGBBGGBGBBBGBBBGBGGBGBGBGGGBGG
BBGBBGGGBGGBGBBBBGBGBGGBBBGGBG
GGGGBGGBGGBGGGGGGBBGBBGGGBGGBG
BBBBGGBGGGGBBBGBGBBBBBGGGGGBBG
BGGGGBGBGBGBGBB...

output:

9

result:

ok single line: '9'

Test #20:

score: 0
Accepted
time: 0ms
memory: 5888kb

input:

30 30
GGBGGGGGBGGBGGBGBGBGGBGGGGGBBB
BGGGBBBBBBBGBBGGGBBGGGBBGGBBGB
BGBGBBBGBGBBGBGBBGBGGBGGBBGBGG
BBBGGBGGGGGBGGBBBBBGBGBGBBGBGG
GGBGGGBBGBGGGGBGGBGBGGBGGBGBGG
BBGGBBGGBGGGGBGBBBBBBBGBGGBGBB
BGBGGBBGBBGBGBGBGBGBGGGGBGGBGB
GGBBBBGGBBGGBGGGGBBGGBBBGBBGGB
GGBGGBGBBBBBBBGGBGBGBBGBBBBBBG
GGBBBBGGGBGGBGB...

output:

9

result:

ok single line: '9'

Test #21:

score: 0
Accepted
time: 1ms
memory: 6540kb

input:

100 100
GGGBGBGGGGBBBGGGBGBGBBGGBBBBBGGGGGBGBBBGBGGGGBGBBBGBBGGGGBBBGGGGGBBGGBGBGGGBBBBGBBGGBBGBBGGBGGGBBBBG
BGGGBBBGGGBGGGGGBBBGBBBBGGGGGBGGBBBBBBGGGGBBBBBGGBBGBBBGGBBBBBBGBGBGBBBBGBBBGBGBGBBGBGBBGBGGBGGBGBBG
GBBBGGGBGBGGGGBBBGBBGGGGBGBBGBGGBBGBBBGBBBGGBGGGBBGBBBGBGGGBGGBGBGBBBBBGGGBGGGGBGBGBGBBBGB...

output:

16

result:

ok single line: '16'

Test #22:

score: 0
Accepted
time: 0ms
memory: 6540kb

input:

100 100
GGGGBGGGBGGGBGGBBGGGGGGBGBBGGBBGBBGGGGGGBBBGGGGBBBBBGBGGGBGBGGBGBBBGBBBBBBBBGGBGBGBGBGGGBGGGBGGGBGGG
BGGGGGGBBGGBGGBGBBGGBBGGBGGBGBGBBGGBBBGBBGGGBBBGBBGBGGGGBBGBGGBBBGGGBBGGBGGGBBBGGBBBGBGBGGGBBBBBBBGB
BGBBGGBBBBGBGGBGBGGBGGBGBBGBBBGBGGBBGBBGGBBGBBBGGGBBGGBGBGGGBGGBGGGGBBBBBBGGBGGGGBBBGGGGBG...

output:

16

result:

ok single line: '16'

Test #23:

score: 0
Accepted
time: 9ms
memory: 25600kb

input:

1000 1000
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

output:

1000000

result:

ok single line: '1000000'

Test #24:

score: 0
Accepted
time: 0ms
memory: 8832kb

input:

300 300
BGBBBBBBGGGBGBGBGBGGGBGGGGBGGBBBBBBBGBBGGBGGBGGBBGBBGGGBGBGBGGGGGBBBGGBBGGBBBGGGBBBBGBBBBGGBBGBBGBGBBGBGGGGGBGBBGBGGBBBGGGBBGGBBBBBGBGGGGGGBBBGGGGBGBBBBBGGBBBBGGBGBBGGGGBGGGGBBGGBGGBGGGGGBBGGBBGGBGBBGBBBBBBGGGBBGBGBGBGBBGGGBBGGGBBGBGGBGGBBBGGGGGGGGGBGBGBBBGBGBGBGGBGBGGBBGBBBGGBGGBBBGBGBGBBBB...

output:

16

result:

ok single line: '16'

Test #25:

score: 0
Accepted
time: 0ms
memory: 8832kb

input:

300 300
BBBBBGGGBGGBGGBBGBBBGGGGGBGBBGGGBGGBGGBBBGBGGGGBBGGBBBBGBBBGGBGGBGGGGBBGBBGGBGGGBGGGBGGBBGBBGGGGBBGBBGBBBBBBGBBBBBBGGGBBGGGBGBGGBBBBBBGGGGBGGGBGGGBBGGBGBGBGGGBBGGGBBBBGGBBBGBGBBBGBGBBBBGGBGGGGGBBBBGGGGGGGGGGBBBGBBBGBBGGGGBBBBBGBBGGBBBGBBBGGGGGBBGBGGBGBGGBGGGBBGGBGBGGGGGBGGBBBGBBGGBGBBGBGBBGG...

output:

16

result:

ok single line: '16'

Test #26:

score: 0
Accepted
time: 3ms
memory: 11604kb

input:

500 500
GBGBBGGBBGGBGGGGGBGGBGBBBGGBBBGBGGBBGBGGBBGBGGBBGGGGBBBBBGGGBBBBBBBGGGGGGBGGBGGGGBGBBGGGGBBGGGGBBGGGGBGGBGGGBGGGBBBBBBGBBBGGBGGGGBBBGGGBBBBBBBBGGGBGBBGBGGGGGBGGGBGGGBGBGBBGGBGBBBGGBBGGGGGBBGBBGBBGBGGBBBGBGGGBBGBGGBBBGGBGGBGGGBBGBBBBGGBBGBGBBGGGBBBGBBGGBBBGGBBBBGGGBBBBBGBBGBGGGBBGBGBGBGGBGBGG...

output:

25

result:

ok single line: '25'

Test #27:

score: 0
Accepted
time: 2ms
memory: 11608kb

input:

500 500
BBGBBGBGGBGGGGGBBBGBBBBBGGBGBBBGBGBBBGGBBBBBGBGBBBBGBGBGBGGGBBGGBGGGGBBGBBGBBBBGBBGBGGBGGBBBBBGBBBBGGGGBGGGGBGGBGGGBGGGGBGBBBBBGGBBBBBBGBBBGGGBBGBBGGBGGBGGBGBGBBGGBGGGGGGBBGGGBGBBBBGGGGBBBGBGBBGBGBBBGGBGGGBGGBBGGBGBGBGBGBBGBGGGGGGGGBGGGBBBGGGGGBBBGGGGGGGBBGGBGGBBBBGGGBGGBBBGBBBBGBBBBGGGGGGGB...

output:

16

result:

ok single line: '16'

Test #28:

score: 0
Accepted
time: 18ms
memory: 25384kb

input:

1000 1000
GBGBBBGBBGBGBBGBBBGBGBGBGBGGGGBBGBBGBGBGBBGGGBGGBBBGBGBGBBGBGBBGGBGBGGBBGGGGGGGBGBGGGBBBGGBBBGGGBGBGGBGBBBBGBGBGGGGBGGBBBGGGGBGGBGBGGGGBGBGGGBGBBBBBGGGGBBGGGGBBBGBGBBGBBBGBBBGGBGGBGGGGGBGBGBBBBGBBBGBGBGBGBBBGGBBGGGGGBGBBGBBBGGGGGBBBGBBBBGGBGBGGGBGGGBBBGGGGBBGBGBBBBGGGGGBBGBGBBBBGGGGBBBGGGB...

output:

16

result:

ok single line: '16'

Test #29:

score: 0
Accepted
time: 24ms
memory: 24388kb

input:

1000 1000
GGBBGGBBGBBGGGBBGGGBGBBGGBGBBBBBBBBGGGGBGGBBGBGBBGGBGBGGBBGBBGBBBBGBBBBGBBBBGGGBBGGBBBBBGBGGGGBGBGGBGGGGBGGGGBBGGBGBBGGBGBGBGGBBBBGGBBGBBBBBGBBGBBBGBGGGBBBGGBBBBBGGBBGGBGBBBGBGGGBBBBGBBBBGGBBGGBGBBBGBBBGGBGGGGGBBGGGGBBGBBGGGBBGBGBGGBBGGGGGGBGBBGBGBBBBGGGBBBGBBGBGGGGGGGBGBBGGGBGBGGGGGBGGGGB...

output:

25

result:

ok single line: '25'

Test #30:

score: 0
Accepted
time: 6ms
memory: 26044kb

input:

1000 1000
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

1000000

result:

ok single line: '1000000'

Test #31:

score: 0
Accepted
time: 14ms
memory: 23344kb

input:

1000 1000
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

output:

998001

result:

ok single line: '998001'

Test #32:

score: 0
Accepted
time: 1ms
memory: 5652kb

input:

3 3
BBB
BGB
BBB

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 0ms
memory: 8848kb

input:

300 300
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

output:

90000

result:

ok single line: '90000'

Test #34:

score: 0
Accepted
time: 3ms
memory: 10596kb

input:

300 300
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

90000

result:

ok single line: '90000'

Test #35:

score: 0
Accepted
time: 1ms
memory: 5740kb

input:

1 1
G

output:

1

result:

ok single line: '1'