oj.uz

Submission #303901

# Submission time Handle Problem Language Result Execution time Memory
303901 2020-09-20T18:18:31 Z pit4h Dango Maker (JOI18_dango_maker) C++14
0 / 100
 2 ms 512 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 3001;
int n, m, nr;
int matched[N * N], vis[N * N];
int iter;
bool horiz[N][N], vert[N][N];
string tab[N];
vector<int> vx = {0, -1, -2}, vy = {0, 1, 2};
bool ok(int x, int y) {
	if(x>=0 && y<m && horiz[x][y]) return true;
	return false;
}
int convert(int x, int y) {
	return x*m + y;
}
bool match(int x) {
	vis[x] = iter;
	for(int i=0; i<3; ++i) {
		int X = x/m, Y = x%m;
		int rep = convert(X+vx[i], Y+vy[i]);
		if(ok(X+vx[i], Y+vy[i]) && matched[rep]==-1) {
			matched[rep] = x;
			return true;
		}
	}
	for(int i=0; i<3; ++i) {
		int X = x/m, Y = x%m;
		int rep = convert(X+vx[i], Y+vy[i]);
		if(ok(X+vx[i], Y+vy[i]) && vis[rep] != iter && match(rep)) {
			matched[rep] = x;
			return true;
		}
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=0; i<n; ++i) {
		cin>>tab[i];
	}
	int sz = 0;
	vector<int> cand;
	for(int i=0; i<n; ++i) { // left - right
		for(int j=0; j+2<m; ++j) {
			if(tab[i][j] == 'R' && tab[i][j+1] == 'G' && tab[i][j+2] == 'W') {
				vert[i][j] = 1;
				sz++;
				cand.push_back(convert(i, j));
			}
		}
	}
	for(int i=0; i+2<n; ++i) { // top - bottom 
		for(int j=0; j<m; ++j) {
			if(tab[i][j] == 'R' && tab[i+1][j] == 'G' && tab[i+2][j] == 'W') {
				horiz[i][j] = 1;
				nr++;
			}
		}
	}
	for(int i=0; i<nr; ++i) {
		matched[i] = -1;
	}
	int ans = 0;
	for(int i=0; i<sz; ++i) {
		iter++;
		match(cand[i]);
	}
	for(int i=0; i<nr; ++i) {
		if(matched[i] != -1) {
			ans++;
		}
	}
	cout<<nr + sz - ans;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 512 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 512 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 512 KB Output isn't correct
7 Halted 0 ms 0 KB -