Submission #814822

#TimeUsernameProblemLanguageResultExecution timeMemory
814822CookieDango Maker (JOI18_dango_maker)C++14
100 / 100
302 ms35632 KiB
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
// int y[4] = {0, 0, 1, -1};
const ll mod = 1e15 + 7, inf = 1e16;
const int mxn = 2e5 + 5;
int n, m;
int dp[3005][3];
char a[3005][3005];
bool up[3005][3005], rght[3005][3005];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    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++){
            if(a[i][j] == 'G'){
                if(a[i - 1][j] == 'R' && a[i + 1][j] == 'W')up[i][j] = 1;
                if(a[i][j - 1] == 'R' && a[i][j + 1] == 'W')rght[i][j] = 1;
            }
        }
    }
    int ans =0 ;
    for(int i = 2; i <= n + m; i++){
        for(int j = 1; j <= n; j++){
            dp[j][0] = dp[j][1] = dp[j][2] = 0;
        }
        for(int j = max(i - m, 1); j <= min(i - 1, n); j++){
            int col = i - j;
            dp[j][0] = max({dp[j - 1][0], dp[j - 1][1], dp[j - 1][2]});
            if(up[j][col]){
                dp[j][2] = max(dp[j - 1][0], dp[j - 1][2]) + 1;
            }else dp[j][2] = 0;
            if(rght[j][col]){
                dp[j][1] = max(dp[j - 1][0], dp[j - 1][1]) + 1;
            }else dp[j][1] = 0;
        }
        ans += max({dp[min(i - 1, n)][0], dp[min(i - 1, n)][1], dp[min(i - 1, n)][2]});
    }
    cout << ans;
    return(0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...