Submission #141691

#	Time	Username	Problem	Language	Result	Execution time	Memory
141691		osaaateiasavtnl	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	284 ms	18168 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
const int N = 3001; char a[N][N];
int dp[N << 1][3];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, m; cin >> n >> m; 
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> a[i][j];
    int ans = 0;
    for (int sum = 0; sum < 2 * N; ++sum) {
        for (int i = 0; i < N; ++i) for (int j = 0; j < 3; ++j) dp[i][j] = -N;
        int tmp = max(0ll, sum - m + 1);
        dp[tmp][0] = 0; int r = tmp;
        for (int i = tmp; i <= sum && i < n; ++i) {
            int j = sum - i;
            int t = -N; for (int k = 0; k < 3; ++k) dp[i + 1][0] = max(dp[i + 1][0], dp[i][k]);
            if (a[i][j] == 'G' && i && a[i - 1][j] == 'R' && a[i + 1][j] == 'W') dp[i + 1][1] = max(dp[i][0], dp[i][1]) + 1;
            if (a[i][j] == 'G' && j && a[i][j - 1] == 'R' && a[i][j + 1] == 'W') dp[i + 1][2] = max(dp[i][0], dp[i][2]) + 1;
            r = i + 1;
        }
        int add = 0;
        for (int i = 0; i < 3; ++i) add = max(add, dp[r][i]);
        ans += add;
    }
    cout << ans << '\n';
}   

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:24:17: warning: unused variable 't' [-Wunused-variable]
             int t = -N; for (int k = 0; k < 3; ++k) dp[i + 1][0] = max(dp[i + 1][0], dp[i][k]);
                 ^

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