oj.uz

Submission #644006

# Submission time Handle Problem Language Result Execution time Memory
644006 2022-09-23T12:58:00 Z tokyo682 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 400 KB 
#include<bits/stdc++.h>

using namespace std;
 
int dp[3001][3001][3];
string table[3001];

int main(){
    
    int m , n ; cin >> m >> n ;

    for(int i = 1 ; i <= m ; i ++ ){
        cin >> table[i] ;
        table[i] = ' ' + table[i] ;
    }

    for(int i = 1 ; i <= m ; i ++ ){
        for(int j = 1 ; j <= n ; j ++ ){
            if(table[i][j] == 'G'){
                if(j > 1 && j < n){
                    if(table[i][j - 1] == 'R' && table[i][j + 1] == 'W'){
                        dp[i][j][1] = max(dp[i - 1][j + 1][1] , dp[i - 1][j + 1][0]) + 1 ;
                    }
                }
                if(i > 1 && i < m){
                    if(table[i - 1][j] == 'R' && table[i + 1][j] == 'W'){
                        dp[i][j][2] = max(dp[i - 1][j + 1][2] , dp[i - 1][j + 1][0]) + 1 ;
                    }
                }
            }
            dp[i][j][0] = max({dp[i - 1][j + 1][0] , dp[i - 1][j + 1][1] , dp[i - 1][j + 1][2]}) ;
        }
    }
    
    int res = 0 ;
    for(int i = 1 ; i <= m ; i ++ ){
        res += max({dp[i][1][0] , dp[i][1][1] , dp[i][1][2]});
    }
    for(int j = 1 ; j <= n ; j ++ ){
        res += max({dp[m][j][0] , dp[m][j][1] , dp[m][j][2]}) ;
    }
    res -= max({dp[n][1][0] , dp[n][1][1] , dp[n][1][2]});

    cout << res ;
    
    // for(int i = 1 ; i <= m ; i ++ ){
    //     for(int j = 1 ; j <= n ; j ++){
    //         cout << max({dp[i][j][0] , dp[i][j][1] , dp[i][j][2]});
    //     }
    //     cout << '\n';
    // }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 396 KB Output is correct
6 Correct 0 ms 396 KB Output is correct
7 Correct 1 ms 396 KB Output is correct
8 Correct 0 ms 400 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 396 KB Output is correct
6 Correct 0 ms 396 KB Output is correct
7 Correct 1 ms 396 KB Output is correct
8 Correct 0 ms 400 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 0 ms 340 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 396 KB Output is correct
6 Correct 0 ms 396 KB Output is correct
7 Correct 1 ms 396 KB Output is correct
8 Correct 0 ms 400 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 0 ms 340 KB Output isn't correct
20 Halted 0 ms 0 KB -