Submission #678550

#	Time	Username	Problem	Language	Result	Execution time	Memory
678550		vjudge1	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	340 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;
typedef long double ld;
typedef pair<int, pair<int, int>> ft;

const ld PI = acos(-1);
const int maxn = 3e3+5;
const ll inf = 1e18;
const int mod = 998244353;

int n, m;

ll ans = 0, mx = -inf;

char board[maxn][maxn];
int dp[maxn][maxn][4];
int st[maxn][maxn];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)cin >> board[i][j];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(j+2 <= m && board[i][j] == 'R' && board[i][j+1] == 'G' && board[i][j+2] == 'W'){
                st[i][j]^=1;
            }
            if(i+2 <= n && board[i][j] == 'R' && board[i+1][j] == 'G' && board[i+2][j] == 'W'){
                st[i][j]^=2;
            }
        }
    }
    for(int i = n; i >= 1; i--){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k < 3; k++){
                dp[i][j][k] = dp[i+1][j-1][k+1];
            }
            dp[i][j][0] = max(dp[i][j][0], dp[i+1][j-1][0]);
            if(st[i][j]&2)dp[i][j][0] = max(dp[i][j][0], dp[i+1][j-1][0]+1);
            if(st[i][j]&1){
                for(int k = 0; k < 4; k++)dp[i][j][3] = max(dp[i][j][3], dp[i+1][j-1][k]+1);
            }
            /*for(int k = 0; k < 4; k++){
                cout << i << " " << j << " " << k << " " << dp[i][j][k] << "\n";
            }*/
            if(i == 1 || j == m)ans += max({dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]});
    
        }
    } 
    cout << ans;
}
 

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67