oj.uz

Submission #45665

# Submission time Handle Problem Language Result Execution time Memory
45665 2018-04-15T20:53:15 Z reality Dango Maker (JOI18_dango_maker) C++17
0 / 100
 2 ms 764 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Incorrect 2 ms 764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Incorrect 2 ms 764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Incorrect 2 ms 764 KB Output isn't correct
7 Halted 0 ms 0 KB -