Submission #332537

#	Time	Username	Problem	Language	Result	Execution time	Memory
332537		limabeans	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	896 ms	147308 KiB

dango_maker

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl











const int maxn = 3002;


int n, m;
string g[maxn];


//RGW
bool can[maxn][maxn][4];

vector<pair<int,int>> diag[maxn+maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    for (int i=0; i<n; i++) {
	cin>>g[i];
    }

    // mark centers
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    //vertical
	    if (i>0 && i+1<n) {
		if (g[i-1][j]=='R' && g[i][j]=='G' && g[i+1][j]=='W') {
		    can[i][j][1]=true;
		}
	    }
	    //horizontal
	    if (j>0 && j+1<m) {
		if (g[i][j-1]=='R' && g[i][j]=='G' && g[i][j+1]=='W') {
		    can[i][j][2]=true;
		}
	    }
	}
    }


    
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    diag[i+j].push_back({i,j});
	}
    }


    int res = 0;


    for (int d=0; d<n+m; d++) {
	int len = diag[d].size();
	vector<vector<int>> dp(len+1, vector<int>(3, 0)); //0: none, 1: vert, 2: horiz
	for (int i=1; i<=len; i++) {
	    int x = diag[d][i-1].first;
	    int y = diag[d][i-1].second;

	    dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});

	    for (int op=1; op<=2; op++) {
		if (can[x][y][op]) {
		    dp[i][op] = max({dp[i][op], 1+dp[i-1][0], 1+dp[i-1][op]}); // vert only compatibile with vert along the diagonal
		}
	    }
	}

	res += max({dp[len][0],dp[len][1],dp[len][2]});
    }

    cout<<res<<endl;    
    return 0;
}

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