Submission #303911

#TimeUsernameProblemLanguageResultExecution timeMemory
303911pit4hDango Maker (JOI18_dango_maker)C++14
100 / 100
502 ms117580 KiB
#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 + vx[i], Y = x%m + vy[i]; int rep = convert(X, Y); if(ok(X, Y) && matched[rep]==-1) { matched[rep] = x; return true; } } for(int i=0; i<3; ++i) { int X = x/m + vx[i], Y = x%m + vy[i]; int rep = convert(X, Y); if(ok(X, Y) && vis[matched[rep]] != iter && match(matched[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<n*m; ++i) { matched[i] = -1; } int ans = 0; for(int i=0; i<sz; ++i) { iter++; match(cand[i]); } for(int i=0; i<n*m; ++i) { if(matched[i] != -1) { ans++; } } cout<<nr + sz - ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...