QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53962#85. Leverage MDTnot_so_organicAC ✓80ms21288kbC++201.7kb2022-10-06 13:42:402022-10-06 13:42:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-06 13:42:43]
  • 评测
  • 测评结果:AC
  • 用时:80ms
  • 内存:21288kb
  • [2022-10-06 13:42:40]
  • 提交

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: 0ms
memory: 3664kb

input:

2 2
GG
GG

output:

4

result:

ok single line: '4'

Test #2:

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

input:

1 1
B

output:

1

result:

ok single line: '1'

Test #3:

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

input:

2 2
BB
BB

output:

4

result:

ok single line: '4'

Test #4:

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

input:

2 2
GB
BB

output:

1

result:

ok single line: '1'

Test #5:

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

input:

2 2
BG
BB

output:

1

result:

ok single line: '1'

Test #6:

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

input:

2 2
BB
GB

output:

1

result:

ok single line: '1'

Test #7:

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

input:

2 2
BB
BG

output:

1

result:

ok single line: '1'

Test #8:

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

input:

2 2
BB
GG

output:

4

result:

ok single line: '4'

Test #9:

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

input:

2 2
BG
BG

output:

1

result:

ok single line: '1'

Test #10:

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

input:

2 2
BG
BG

output:

1

result:

ok single line: '1'

Test #11:

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

input:

2 2
GG
GG

output:

4

result:

ok single line: '4'

Test #12:

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

input:

5 5
GGGGG
GBBBG
GBBBG
GBBBG
GGGGG

output:

9

result:

ok single line: '9'

Test #13:

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

input:

5 1
G
G
G
G
G

output:

1

result:

ok single line: '1'

Test #14:

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

input:

5 1
G
B
G
G
G

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1 5
GGGGG

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 5
GBGGG

output:

1

result:

ok single line: '1'

Test #17:

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

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: 1ms
memory: 3636kb

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: 2ms
memory: 3844kb

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: 2ms
memory: 3984kb

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: 3ms
memory: 4680kb

input:

100 100
GGGBGBGGGGBBBGGGBGBGBBGGBBBBBGGGGGBGBBBGBGGGGBGBBBGBBGGGGBBBGGGGGBBGGBGBGGGBBBBGBBGGBBGBBGGBGGGBBBBG
BGGGBBBGGGBGGGGGBBBGBBBBGGGGGBGGBBBBBBGGGGBBBBBGGBBGBBBGGBBBBBBGBGBGBBBBGBBBGBGBGBBGBGBBGBGGBGGBGBBG
GBBBGGGBGBGGGGBBBGBBGGGGBGBBGBGGBBGBBBGBBBGGBGGGBBGBBBGBGGGBGGBGBGBBBBBGGGBGGGGBGBGBGBBBGB...

output:

16

result:

ok single line: '16'

Test #22:

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

input:

100 100
GGGGBGGGBGGGBGGBBGGGGGGBGBBGGBBGBBGGGGGGBBBGGGGBBBBBGBGGGBGBGGBGBBBGBBBBBBBBGGBGBGBGBGGGBGGGBGGGBGGG
BGGGGGGBBGGBGGBGBBGGBBGGBGGBGBGBBGGBBBGBBGGGBBBGBBGBGGGGBBGBGGBBBGGGBBGGBGGGBBBGGBBBGBGBGGGBBBBBBBGB
BGBBGGBBBBGBGGBGBGGBGGBGBBGBBBGBGGBBGBBGGBBGBBBGGGBBGGBGBGGGBGGBGGGGBBBBBBGGBGGGGBBBGGGGBG...

output:

16

result:

ok single line: '16'

Test #23:

score: 0
Accepted
time: 15ms
memory: 21120kb

input:

1000 1000
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

output:

1000000

result:

ok single line: '1000000'

Test #24:

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

input:

300 300
BGBBBBBBGGGBGBGBGBGGGBGGGGBGGBBBBBBBGBBGGBGGBGGBBGBBGGGBGBGBGGGGGBBBGGBBGGBBBGGGBBBBGBBBBGGBBGBBGBGBBGBGGGGGBGBBGBGGBBBGGGBBGGBBBBBGBGGGGGGBBBGGGGBGBBBBBGGBBBBGGBGBBGGGGBGGGGBBGGBGGBGGGGGBBGGBBGGBGBBGBBBBBBGGGBBGBGBGBGBBGGGBBGGGBBGBGGBGGBBBGGGGGGGGGBGBGBBBGBGBGBGGBGBGGBBGBBBGGBGGBBBGBGBGBBBB...

output:

16

result:

ok single line: '16'

Test #25:

score: 0
Accepted
time: 7ms
memory: 7308kb

input:

300 300
BBBBBGGGBGGBGGBBGBBBGGGGGBGBBGGGBGGBGGBBBGBGGGGBBGGBBBBGBBBGGBGGBGGGGBBGBBGGBGGGBGGGBGGBBGBBGGGGBBGBBGBBBBBBGBBBBBBGGGBBGGGBGBGGBBBBBBGGGGBGGGBGGGBBGGBGBGBGGGBBGGGBBBBGGBBBGBGBBBGBGBBBBGGBGGGGGBBBBGGGGGGGGGGBBBGBBBGBBGGGGBBBBBGBBGGBBBGBBBGGGGGBBGBGGBGBGGBGGGBBGGBGBGGGGGBGGBBBGBBGGBGBBGBGBBGG...

output:

16

result:

ok single line: '16'

Test #26:

score: 0
Accepted
time: 10ms
memory: 10676kb

input:

500 500
GBGBBGGBBGGBGGGGGBGGBGBBBGGBBBGBGGBBGBGGBBGBGGBBGGGGBBBBBGGGBBBBBBBGGGGGGBGGBGGGGBGBBGGGGBBGGGGBBGGGGBGGBGGGBGGGBBBBBBGBBBGGBGGGGBBBGGGBBBBBBBBGGGBGBBGBGGGGGBGGGBGGGBGBGBBGGBGBBBGGBBGGGGGBBGBBGBBGBGGBBBGBGGGBBGBGGBBBGGBGGBGGGBBGBBBBGGBBGBGBBGGGBBBGBBGGBBBGGBBBBGGGBBBBBGBBGBGGGBBGBGBGBGGBGBGG...

output:

25

result:

ok single line: '25'

Test #27:

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

input:

500 500
BBGBBGBGGBGGGGGBBBGBBBBBGGBGBBBGBGBBBGGBBBBBGBGBBBBGBGBGBGGGBBGGBGGGGBBGBBGBBBBGBBGBGGBGGBBBBBGBBBBGGGGBGGGGBGGBGGGBGGGGBGBBBBBGGBBBBBBGBBBGGGBBGBBGGBGGBGGBGBGBBGGBGGGGGGBBGGGBGBBBBGGGGBBBGBGBBGBGBBBGGBGGGBGGBBGGBGBGBGBGBBGBGGGGGGGGBGGGBBBGGGGGBBBGGGGGGGBBGGBGGBBBBGGGBGGBBBGBBBBGBBBBGGGGGGGB...

output:

16

result:

ok single line: '16'

Test #28:

score: 0
Accepted
time: 80ms
memory: 21060kb

input:

1000 1000
GBGBBBGBBGBGBBGBBBGBGBGBGBGGGGBBGBBGBGBGBBGGGBGGBBBGBGBGBBGBGBBGGBGBGGBBGGGGGGGBGBGGGBBBGGBBBGGGBGBGGBGBBBBGBGBGGGGBGGBBBGGGGBGGBGBGGGGBGBGGGBGBBBBBGGGGBBGGGGBBBGBGBBGBBBGBBBGGBGGBGGGGGBGBGBBBBGBBBGBGBGBGBBBGGBBGGGGGBGBBGBBBGGGGGBBBGBBBBGGBGBGGGBGGGBBBGGGGBBGBGBBBBGGGGGBBGBGBBBBGGGGBBBGGGB...

output:

16

result:

ok single line: '16'

Test #29:

score: 0
Accepted
time: 80ms
memory: 21288kb

input:

1000 1000
GGBBGGBBGBBGGGBBGGGBGBBGGBGBBBBBBBBGGGGBGGBBGBGBBGGBGBGGBBGBBGBBBBGBBBBGBBBBGGGBBGGBBBBBGBGGGGBGBGGBGGGGBGGGGBBGGBGBBGGBGBGBGGBBBBGGBBGBBBBBGBBGBBBGBGGGBBBGGBBBBBGGBBGGBGBBBGBGGGBBBBGBBBBGGBBGGBGBBBGBBBGGBGGGGGBBGGGGBBGBBGGGBBGBGBGGBBGGGGGGBGBBGBGBBBBGGGBBBGBBGBGGGGGGGBGBBGGGBGBGGGGGBGGGGB...

output:

25

result:

ok single line: '25'

Test #30:

score: 0
Accepted
time: 13ms
memory: 21128kb

input:

1000 1000
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

1000000

result:

ok single line: '1000000'

Test #31:

score: 0
Accepted
time: 15ms
memory: 21248kb

input:

1000 1000
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

output:

998001

result:

ok single line: '998001'

Test #32:

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

input:

3 3
BBB
BGB
BBB

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 7ms
memory: 7296kb

input:

300 300
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

output:

90000

result:

ok single line: '90000'

Test #34:

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

input:

300 300
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

90000

result:

ok single line: '90000'

Test #35:

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

input:

1 1
G

output:

1

result:

ok single line: '1'