Submission #676940

#	Time	Username	Problem	Language	Result	Execution time	Memory
676940		cristi_a	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	612 ms	68796 KiB

dango_maker

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >>m;
    vector<string> a(n);
    for(int i=0; i<n; i++)
    	cin>>a[i];

    vector<vector<int>> in(n + m);
    for(int i=0; i<n; i++)
    	for(int j=0; j<m; j++)
    		in[i + j].push_back(i);

    auto can = [&](int i, int j){
    	return (0 < j && j+1 < m && a[i][j-1] == 'R' && a[i][j] == 'G' && a[i][j+1] == 'W');
    };

    auto can_ = [&](int i, int j){
    	return (0 < i && i+1 < n && a[i-1][j] == 'R' && a[i][j] == 'G' && a[i+1][j] == 'W');
    };

    int res = 0;
    for(int s=0; s<n+m; s++){
    	int k = in[s].size();
        vector<vector<int>> dp(k+1, vector<int>(3));
    	for(int l=1; l<=k; l++){
    		int i = in[s][l-1], j = s - i;
    		dp[l][0] = max({dp[l-1][0], dp[l-1][1], dp[l-1][2]});
    		if(can(i, j)) dp[l][1] = max(dp[l-1][0], dp[l-1][1]) + 1;
    		if(can_(i, j)) dp[l][2] = max(dp[l-1][0], dp[l-1][2]) + 1;
    	}
    	res += max({dp[k][0], dp[k][1], dp[k][2]});
    }
    	
    cout << res << "\n";
    return 0;
}

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