QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#574869#3125. Dango Makerivan_alexeev13 0ms3896kbC++232.5kb2024-09-19 04:16:572024-09-19 04:16:58

Judging History

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

  • [2024-09-19 04:16:58]
  • 评测
  • 测评结果:13
  • 用时:0ms
  • 内存:3896kb
  • [2024-09-19 04:16:57]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;

const ll inf = 1'000'000'000'000'000'000;

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma,popcnt")


//#define int long long
int n, m;
vector<vector<int>> z;

bool get(int x, int y, bool f){
    if((x >= 0) && (x < n) && (y >= 0) && (y < m)){

    }else{
        return 0;
    }
    if(f){
        if(x + 2 < n){
            return ((z[x][y] == 0) && (z[x + 1][y] == 1) && (z[x + 2][y] == 2));
        }else{
            return 0;
        }
    }else{
        if(y + 2 < m){
            return ((z[x][y] == 0) && (z[x][y + 1] == 1) && (z[x][y + 2] == 2));
        }else{
            return 0;
        }
    }
}

int solve1(vector<int> a, vector<int> b){
    int n = a.size();
    vector<vector<int>> dp(n + 1, vector<int>(3));
    dp[0] = {0, 0, 0};
    for(int i = 0; i < n; i++){
        dp[i + 1][0] = dp[i][0];
        dp[i + 1][1] = dp[i][1];
        dp[i + 1][2] = dp[i][2];
        if(b[i]){
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + 1);
        }
        if(a[i]){
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][2] + 1);
            dp[i + 1][1] = max(dp[i + 1][1], dp[i][2] + 1);
            dp[i + 1][2] = max(dp[i + 1][2], dp[i][2] + 1);
        }
    }
    return dp.back()[0];
}

void solve(){
    cin >> n >> m;
    z.resize(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            if(s[j] == 'R'){
                z[i][j] = 0;
            }else if(s[j] == 'G'){
                z[i][j] = 1;
            }else{
                z[i][j] = 2;
            }
        }
    }
    int ans = 0;
    for(int sum = 0; sum < n + m - 1; sum++){
        vector<int> a, b;
        for(int j = 0; j < m; j++){
            int i = sum - j;
            if((i >= 0) && (i < n)){
                a.push_back(get(i, j, 1));
                b.push_back(get(i, j, 0));
            }
        }
        ans += solve1(a, b);
    }
    cout << ans << endl;
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << setprecision(5) << fixed;
    int _ = 1;
    //cin >> t;
    while(_--){
        solve();
    }
    return 0;
}

詳細信息

Subtask #1:

score: 13
Accepted

Test #1:

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

input:

1 1
G

output:

0

result:

ok single line: '0'

Test #2:

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

input:

1 2
RG

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 1
W
R

output:

0

result:

ok single line: '0'

Test #4:

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

input:

3 2
WW
RW
WR

output:

0

result:

ok single line: '0'

Test #5:

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

input:

4 4
GRRW
GWWR
WWWW
RGRG

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
RGRR
RRRG
GRGW
RGWW

output:

2

result:

ok single line: '2'

Test #7:

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

input:

4 4
RRGR
GRRG
WRGW
RGWW

output:

3

result:

ok single line: '3'

Test #8:

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

input:

4 4
RGWR
GGGW
WWGW
RWGW

output:

1

result:

ok single line: '1'

Test #9:

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

input:

3 3
RGW
GGG
WGW

output:

1

result:

ok single line: '1'

Test #10:

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

input:

4 1
W
R
G
W

output:

1

result:

ok single line: '1'

Test #11:

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

input:

4 4
RGWR
GWRG
WRGW
RGWR

output:

3

result:

ok single line: '3'

Test #12:

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

input:

4 4
RWWR
GWRG
WGGW
RGWR

output:

3

result:

ok single line: '3'

Test #13:

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

input:

4 4
RGWR
WWRG
WRGW
RWGR

output:

2

result:

ok single line: '2'

Test #14:

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

input:

4 4
RRRR
GGGG
WWWW
RRRR

output:

4

result:

ok single line: '4'

Test #15:

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

input:

4 4
RRRR
GGGR
WWWW
RRRR

output:

3

result:

ok single line: '3'

Test #16:

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

input:

4 4
RRRR
GGGG
WWWW
RWRR

output:

4

result:

ok single line: '4'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #17:

score: 20
Accepted
time: 0ms
memory: 3584kb

input:

5 5
RRGRR
RGRGW
RRWRW
RGWGW
RWWWW

output:

3

result:

ok single line: '3'

Test #18:

score: 20
Accepted
time: 0ms
memory: 3644kb

input:

6 6
RGWRGW
RRRGWR
RRWGWR
WRRRWG
GGGGGW
WWWWWW

output:

7

result:

ok single line: '7'

Test #19:

score: 20
Accepted
time: 0ms
memory: 3852kb

input:

7 10
RRRGRGWRGW
RGGGWRRGWR
RWWWWGRRGG
RGWRWWGGGW
WWRGWRGWGW
RGWWGGRGWW
RRGWWWWWWW

output:

14

result:

ok single line: '14'

Test #20:

score: 20
Accepted
time: 0ms
memory: 3684kb

input:

10 8
RGWRRRGW
RGWGRRGW
WRGWGRGW
RGWWRGWW
GWRRGWWW
WRRGRWRR
GRGWGRGG
WGWWWRWR
RGWRGRGW
RRWRGWWW

output:

16

result:

ok single line: '16'

Test #21:

score: 20
Accepted
time: 0ms
memory: 3644kb

input:

10 10
RRRRGWRRGW
GRGRGRGGRR
RGRGWGRRGR
RWWWRRGRGW
GRGGGRGWGG
WRGWWGGRGW
GGGRWWWRRR
WWGRGWRRGG
WWGWGWGGWW
RRGWGRWWWW

output:

16

result:

ok single line: '16'

Test #22:

score: 0
Wrong Answer
time: 0ms
memory: 3588kb

input:

10 10
RRRWRGWRGW
GGGGGGRRWG
WGWRWWGGGW
RRRRRRWRRG
GGGGGGRGGR
WGWWWWGWGW
WRRGWRWRGW
RGWGRGWGRW
GRWRGWWWGG
RGWWGWRGWW

output:

17

result:

wrong answer 1st lines differ - expected: '19', found: '17'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%