#include<bits/stdc++.h>
using namespace std;
typedef int ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int MAXN = 3e6;
struct edge{
int to;
ll cap;
int rev;
};
vector<edge> side[MAXN];
int level[MAXN];
int nxt[MAXN];
struct DINIC{
int n;
void init(int s){
n = s;
for(int i=0;i<n;i++) side[i].clear();
}
void add_edge(int a,int b,ll c){
// cout<<a<<"->"<<b<<"\n";
side[a].push_back({b,c,(int)(side[b].size())});
side[b].push_back({a,0,(int)(side[a].size()-1)});
}
bool bfs(int s,int t){
fill(level,level+n,-1);
queue<int> q;
level[s]=0;
q.push(s);
while(q.size()){
int cur = q.front();
q.pop();
for(auto e : side[cur]){
if(e.cap<=0) continue;
if(level[e.to]<0){
level[e.to] = level[cur]+1;
q.push(e.to);
}
}
}
return (level[t]!=-1);
}
ll dfs(int v,int t,ll flow){
if(v==t) return flow;
for(;nxt[v]<side[v].size();nxt[v]++){
auto& e = side[v][nxt[v]];
if(e.cap<=0 || level[v]+1!=level[e.to]) continue;
ll ans = dfs(e.to,t,min(flow,e.cap));
if(ans>0){
e.cap-=ans;
side[e.to][e.rev].cap+=ans;
return ans;
}
}
return 0;
}
ll flow(int s,int t){
ll ans= 0;
while(bfs(s,t)){
fill(nxt,nxt+n,0);
ll f = 0;
while((f=dfs(s,t,1e9))>0){
ans+=f;
}
}
return ans;
}
} graph;
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
vector<vector<char>> grid(n,vector<char>(m));
vector<vector<int> > taken(n,vector<int>(m,0));
for(int i=0;i<n;i++){
string s;cin>>s;
for(int j=0;j<m;j++){
grid[i][j] = s[j];
}
}
int cnt = 0;
for(int i=0;i<n;i++){
for(int j=0;j+2<m;j++){
if(grid[i][j]=='R' && grid[i][j+1]=='G' && grid[i][j+2]=='W'){
cnt++;
taken[i][j]=cnt;
taken[i][j+1]=cnt;
taken[i][j+2]=cnt;
}
}
}
//cout<<cnt<<" ";
int total = cnt;
for(int j=0;j<m;j++){
for(int i=0;i+2<n;i++){
total+=(grid[i][j]=='R' && grid[i+1][j]=='G' && grid[i+2][j]=='W');
}
}
//cout<<total<<"\n";
graph.init(total+2) ;
int ton = cnt;
for(int j=0;j<m;j++){
for(int i=0;i+2<n;i++){
if(grid[i][j]=='R' && grid[i+1][j]=='G' && grid[i+2][j]=='W'){
ton++;
if(taken[i][j]) graph.add_edge(taken[i][j],ton,1);
if(taken[i+1][j]) graph.add_edge(taken[i+1][j],ton,1);
if(taken[i+2][j]) graph.add_edge(taken[i+2][j],ton,1);
}
}
}
for(int i=1;i<=cnt;i++){
graph.add_edge(0,i,1);
}
for(int i=cnt+1;i<=total;i++){
graph.add_edge(i,total+1,1);
}
ll ans = graph.flow(0,total+1);
cout<<total-ans<<"\n";
return 0;
}
Compilation message
dango_maker.cpp: In member function 'll DINIC::dfs(int, int, ll)':
dango_maker.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(;nxt[v]<side[v].size();nxt[v]++){
| ~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
73560 KB |
Output is correct |
2 |
Correct |
15 ms |
73560 KB |
Output is correct |
3 |
Correct |
16 ms |
73560 KB |
Output is correct |
4 |
Correct |
15 ms |
73560 KB |
Output is correct |
5 |
Correct |
15 ms |
73560 KB |
Output is correct |
6 |
Correct |
15 ms |
73560 KB |
Output is correct |
7 |
Correct |
15 ms |
73560 KB |
Output is correct |
8 |
Correct |
17 ms |
73564 KB |
Output is correct |
9 |
Correct |
16 ms |
73560 KB |
Output is correct |
10 |
Correct |
16 ms |
73560 KB |
Output is correct |
11 |
Correct |
16 ms |
73560 KB |
Output is correct |
12 |
Correct |
15 ms |
73664 KB |
Output is correct |
13 |
Correct |
15 ms |
73560 KB |
Output is correct |
14 |
Correct |
16 ms |
73560 KB |
Output is correct |
15 |
Correct |
16 ms |
73564 KB |
Output is correct |
16 |
Correct |
15 ms |
73564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
73560 KB |
Output is correct |
2 |
Correct |
15 ms |
73560 KB |
Output is correct |
3 |
Correct |
16 ms |
73560 KB |
Output is correct |
4 |
Correct |
15 ms |
73560 KB |
Output is correct |
5 |
Correct |
15 ms |
73560 KB |
Output is correct |
6 |
Correct |
15 ms |
73560 KB |
Output is correct |
7 |
Correct |
15 ms |
73560 KB |
Output is correct |
8 |
Correct |
17 ms |
73564 KB |
Output is correct |
9 |
Correct |
16 ms |
73560 KB |
Output is correct |
10 |
Correct |
16 ms |
73560 KB |
Output is correct |
11 |
Correct |
16 ms |
73560 KB |
Output is correct |
12 |
Correct |
15 ms |
73664 KB |
Output is correct |
13 |
Correct |
15 ms |
73560 KB |
Output is correct |
14 |
Correct |
16 ms |
73560 KB |
Output is correct |
15 |
Correct |
16 ms |
73564 KB |
Output is correct |
16 |
Correct |
15 ms |
73564 KB |
Output is correct |
17 |
Correct |
15 ms |
73560 KB |
Output is correct |
18 |
Correct |
16 ms |
73564 KB |
Output is correct |
19 |
Correct |
16 ms |
73560 KB |
Output is correct |
20 |
Correct |
15 ms |
73560 KB |
Output is correct |
21 |
Correct |
15 ms |
73560 KB |
Output is correct |
22 |
Correct |
15 ms |
73560 KB |
Output is correct |
23 |
Correct |
15 ms |
73564 KB |
Output is correct |
24 |
Correct |
16 ms |
73704 KB |
Output is correct |
25 |
Correct |
15 ms |
73560 KB |
Output is correct |
26 |
Correct |
16 ms |
73560 KB |
Output is correct |
27 |
Correct |
16 ms |
73560 KB |
Output is correct |
28 |
Correct |
15 ms |
73560 KB |
Output is correct |
29 |
Correct |
16 ms |
73560 KB |
Output is correct |
30 |
Correct |
15 ms |
73560 KB |
Output is correct |
31 |
Correct |
15 ms |
73696 KB |
Output is correct |
32 |
Correct |
17 ms |
73560 KB |
Output is correct |
33 |
Correct |
16 ms |
73560 KB |
Output is correct |
34 |
Correct |
16 ms |
73560 KB |
Output is correct |
35 |
Correct |
15 ms |
73560 KB |
Output is correct |
36 |
Correct |
17 ms |
73816 KB |
Output is correct |
37 |
Correct |
15 ms |
73560 KB |
Output is correct |
38 |
Correct |
15 ms |
73560 KB |
Output is correct |
39 |
Correct |
15 ms |
73560 KB |
Output is correct |
40 |
Correct |
16 ms |
73572 KB |
Output is correct |
41 |
Correct |
15 ms |
73560 KB |
Output is correct |
42 |
Correct |
15 ms |
73564 KB |
Output is correct |
43 |
Correct |
16 ms |
73560 KB |
Output is correct |
44 |
Correct |
16 ms |
73560 KB |
Output is correct |
45 |
Correct |
15 ms |
73564 KB |
Output is correct |
46 |
Correct |
15 ms |
73560 KB |
Output is correct |
47 |
Correct |
15 ms |
73560 KB |
Output is correct |
48 |
Correct |
15 ms |
73560 KB |
Output is correct |
49 |
Correct |
15 ms |
73560 KB |
Output is correct |
50 |
Correct |
15 ms |
73560 KB |
Output is correct |
51 |
Correct |
15 ms |
73560 KB |
Output is correct |
52 |
Correct |
16 ms |
73560 KB |
Output is correct |
53 |
Correct |
15 ms |
73560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
73560 KB |
Output is correct |
2 |
Correct |
15 ms |
73560 KB |
Output is correct |
3 |
Correct |
16 ms |
73560 KB |
Output is correct |
4 |
Correct |
15 ms |
73560 KB |
Output is correct |
5 |
Correct |
15 ms |
73560 KB |
Output is correct |
6 |
Correct |
15 ms |
73560 KB |
Output is correct |
7 |
Correct |
15 ms |
73560 KB |
Output is correct |
8 |
Correct |
17 ms |
73564 KB |
Output is correct |
9 |
Correct |
16 ms |
73560 KB |
Output is correct |
10 |
Correct |
16 ms |
73560 KB |
Output is correct |
11 |
Correct |
16 ms |
73560 KB |
Output is correct |
12 |
Correct |
15 ms |
73664 KB |
Output is correct |
13 |
Correct |
15 ms |
73560 KB |
Output is correct |
14 |
Correct |
16 ms |
73560 KB |
Output is correct |
15 |
Correct |
16 ms |
73564 KB |
Output is correct |
16 |
Correct |
15 ms |
73564 KB |
Output is correct |
17 |
Correct |
15 ms |
73560 KB |
Output is correct |
18 |
Correct |
16 ms |
73564 KB |
Output is correct |
19 |
Correct |
16 ms |
73560 KB |
Output is correct |
20 |
Correct |
15 ms |
73560 KB |
Output is correct |
21 |
Correct |
15 ms |
73560 KB |
Output is correct |
22 |
Correct |
15 ms |
73560 KB |
Output is correct |
23 |
Correct |
15 ms |
73564 KB |
Output is correct |
24 |
Correct |
16 ms |
73704 KB |
Output is correct |
25 |
Correct |
15 ms |
73560 KB |
Output is correct |
26 |
Correct |
16 ms |
73560 KB |
Output is correct |
27 |
Correct |
16 ms |
73560 KB |
Output is correct |
28 |
Correct |
15 ms |
73560 KB |
Output is correct |
29 |
Correct |
16 ms |
73560 KB |
Output is correct |
30 |
Correct |
15 ms |
73560 KB |
Output is correct |
31 |
Correct |
15 ms |
73696 KB |
Output is correct |
32 |
Correct |
17 ms |
73560 KB |
Output is correct |
33 |
Correct |
16 ms |
73560 KB |
Output is correct |
34 |
Correct |
16 ms |
73560 KB |
Output is correct |
35 |
Correct |
15 ms |
73560 KB |
Output is correct |
36 |
Correct |
17 ms |
73816 KB |
Output is correct |
37 |
Correct |
15 ms |
73560 KB |
Output is correct |
38 |
Correct |
15 ms |
73560 KB |
Output is correct |
39 |
Correct |
15 ms |
73560 KB |
Output is correct |
40 |
Correct |
16 ms |
73572 KB |
Output is correct |
41 |
Correct |
15 ms |
73560 KB |
Output is correct |
42 |
Correct |
15 ms |
73564 KB |
Output is correct |
43 |
Correct |
16 ms |
73560 KB |
Output is correct |
44 |
Correct |
16 ms |
73560 KB |
Output is correct |
45 |
Correct |
15 ms |
73564 KB |
Output is correct |
46 |
Correct |
15 ms |
73560 KB |
Output is correct |
47 |
Correct |
15 ms |
73560 KB |
Output is correct |
48 |
Correct |
15 ms |
73560 KB |
Output is correct |
49 |
Correct |
15 ms |
73560 KB |
Output is correct |
50 |
Correct |
15 ms |
73560 KB |
Output is correct |
51 |
Correct |
15 ms |
73560 KB |
Output is correct |
52 |
Correct |
16 ms |
73560 KB |
Output is correct |
53 |
Correct |
15 ms |
73560 KB |
Output is correct |
54 |
Correct |
15 ms |
73760 KB |
Output is correct |
55 |
Correct |
16 ms |
73804 KB |
Output is correct |
56 |
Correct |
17 ms |
73816 KB |
Output is correct |
57 |
Correct |
16 ms |
74072 KB |
Output is correct |
58 |
Correct |
47 ms |
84752 KB |
Output is correct |
59 |
Correct |
413 ms |
162036 KB |
Output is correct |
60 |
Correct |
434 ms |
161228 KB |
Output is correct |
61 |
Correct |
447 ms |
163312 KB |
Output is correct |
62 |
Correct |
16 ms |
73560 KB |
Output is correct |
63 |
Correct |
406 ms |
158376 KB |
Output is correct |
64 |
Runtime error |
192 ms |
243280 KB |
Execution killed with signal 11 |
65 |
Halted |
0 ms |
0 KB |
- |