Submission #45665

#	Time	Username	Problem	Language	Result	Execution time	Memory
45665		reality	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	2 ms	764 KiB

dango_maker

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int M = 4096;
const int N = M * M;
char str[M][M];
bool ok[M][M][2];
int color[M][M][2];
int cnt1 = 0,cnt2 = 0;
pair < pii , int > dp[M];
int wall[M][M];
int main(void) {
    int n,m;
    cin>>n>>m;
    for (int i = 1;i <= n;++i)
    	cin>>(str[i] + 1);
    string C = "RGW";
    for (int i = 1;i <= n;++i)
    	for (int j = 1;j <= m;++j) {
    		string s = "";
    		s += str[i][j];
    		s += str[i + 1][j];
    		s += str[i + 2][j];
    		if (s == C)
    			ok[i][j][0] = 1;
    		s = "";
    		s += str[i][j];
    		s += str[i][j + 1];
    		s += str[i][j + 2];
    		if (s == C)
    			ok[i][j][1] = 1;
    	}
    int ans = 0;
    int was = 0;
    for (int i = 1;i <= n;++i) {
    	for (int j = 1;j <= m;++j) {
    		dp[j] = dp[j - 1];
    		auto pr = dp[j - 1];
    		if (!wall[i][j] && !wall[i + 1][j] && !wall[i + 2][j])
	    		smax(dp[j],mp(mp(pr.fi.fi,pr.fi.se + ok[i][j][0]),j - 1));
    		if (j >= 3 && !wall[i][j - 2] && !wall[i][j - 1] && !wall[i][j]) {
    			pr = dp[j - 3];
    			smax(dp[j],mp(mp(pr.fi.fi + ok[i][j - 2][1],pr.fi.se),j - 3));
    		}
    	}
    	ans += dp[m].fi.fi + dp[m].fi.se;
    	int cnt = m;
    	while (cnt) {
    		int prev = dp[cnt].se;
    		if (dp[cnt].fi != dp[prev].fi) {
    			if (dp[cnt].fi.fi != dp[prev].fi.fi)
    				wall[i][cnt - 2] = wall[i][cnt - 1] = wall[i][cnt] = ++was;
    			else
    				wall[i][cnt] = wall[i + 1][cnt] = wall[i + 2][cnt] = ++was;
    		}
    		cnt = prev;
    	}
    }
    cout << ans << '\n';
    return 0;
}

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