Submission #164511

#TimeUsernameProblemLanguageResultExecution timeMemory
164511balbitDango Maker (JOI18_dango_maker)C++14
33 / 100
518 ms262148 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define ll long long #define f first #define s second #define FOR(i,a,b) for (int i = a; i<b; i++) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) for (int i = n-1; i>=0; i--) #define SZ(x) (int)(x.size()) #define ALL(x) x.begin(),x.end() #define MX(a,b) a = max(a,(__typeof__(a))(b)) #define MN(a,b) a = min(a,(__typeof__(a))(b)) #define pb push_back #ifdef BALBIT #define IOS() #define bug(x) cerr<<__LINE__<<' '<<#x<<": "<<x<<endl #else #define IOS() ios::sync_with_stdio(0),cin.tie(0) #define endl '\n' #define bug(x) #endif const ll mod = 1e9+7; const int maxn = 3e3+5; const ll INF = 0x3f3f3f3f3f3f3f3f; const int iinf = 0x3f3f3f3f; struct Edge{ int to, rev; int cap; int flow = 0; Edge(int to, int rev, int cap) : to(to),rev(rev),cap(cap){ } }; int N , S, T; vector<vector<Edge> > g; vector<int> level; vector<int> ptr; void add(int v, int u, int cap){ g[v].pb({u,SZ(g[u]), cap}); g[u].pb({v,SZ(g[v])-1, 0}); } bool bfs(){ fill(ALL(level), -1); level[S]=0; queue<int> q ({S}); while (level[T]==-1 && !q.empty() ){ int v = q.front(); q.pop(); for (Edge &e : g[v]){ if(e.cap-e.flow > 0 && level[e.to] == -1){ level[e.to] = level[v]+1; q.push(e.to); } } } return level[T]!=-1; } int dfs(int v, int amt){ if(amt == 0 || v== T) return amt; for(; ptr[v] < SZ(g[v]); ptr[v]++){ Edge &e = g[v][ptr[v]]; if (level[e.to]!=level[v]+1) continue; int mo = dfs(e.to, min(amt,e.cap-e.flow)); if (mo !=0 ) { e.flow += mo; g[e.to][e.rev].flow -= mo; return mo; } } return 0; } int mf(){ int re = 0; while (bfs()){ fill(ALL(ptr),0); while(int amt = dfs(S,iinf)) { re += amt; } } return re; } char grd[maxn][maxn]; int idup[maxn][maxn]; int idrt[maxn][maxn]; signed main(){ IOS(); int n, m; cin>>n>>m; REP(i,n) REP(j,m) cin>>grd[i][j]; int nup = 0, nrt = 0; memset(idup, -1, sizeof(idup)); memset(idrt, -1, sizeof(idrt)); REP(i,n)REP(j,m){ if(grd[i][j]=='G'){ if (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' ) { idup[i][j] = nup++; } if (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' ) { idrt[i][j] = nrt ++; } } } N = nup + nrt + 5; S = N-1, T = N-2; g.resize(N); ptr.resize(N); level.resize(N); REP(i,n) REP(j,m){ if(idup[i][j]!=-1){ // cout<<i<<' '<<j<<' '<<idup[i][j]<<endl; add(S,idup[i][j],1); if(idrt[i][j] != -1) { add(idup[i][j], idrt[i][j] + nup, iinf); } if(i && idrt[i-1][j+1]!=-1){ add(idup[i][j], idrt[i-1][j+1] + nup, iinf); } if(j && idrt[i+1][j-1]!=-1){ add(idup[i][j], idrt[i+1][j-1] + nup, iinf); } } if(idrt[i][j]!=-1){ add(idrt[i][j] + nup, T, 1); } } cout<<nup + nrt - mf() << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...