Submission #132817

#	Time	Username	Problem	Language	Result	Execution time	Memory
132817		Gustav	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	1363 ms	44888 KiB

dango_maker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 998244353;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl

int n, m;
vvi a;

int main(){
    cin >> n >> m;
    a = vvi(n, vi(m));
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            if(s[j] == 'G') a[i][j] = 1;
            else if(s[j] == 'W') a[i][j] = 2;
        }
    }

    int ans = 0;
    for(int k = 0; k < n+m-1; k++){
        int c = k;
        int r = 0;
        if(c >= m){
            r = c-m+1;
            c = m-1;
        }
        vvi dp(min(c+1,n-r)+1, vi(3));
        int pos = min(c,n-r-1);
        while(r < n && c >= 0){
            dp[pos][0] = dp[pos+1][0];
            dp[pos][1] = dp[pos+1][0];
            dp[pos][2] = dp[pos+1][1];
            if(c + 2 < m && a[r][c] == 0 && a[r][c+1] == 1 && a[r][c+2] == 2){
                dp[pos][0] = max(dp[pos][0], dp[pos+1][2] + 1);
                dp[pos][1] = max(dp[pos][1], dp[pos+1][2] + 1);
                dp[pos][2] = max(dp[pos][2], dp[pos+1][2] + 1);
            }
            if(r + 2 < n && a[r][c] == 0 && a[r+1][c] == 1 && a[r+2][c] == 2){
                dp[pos][0] = max(dp[pos][0], dp[pos+1][0] + 1);
            }
            r++;
            c--;
            pos--;
        }
        ans += dp[0][0];
    }
    cout << ans << "\n";
}

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