結果
問題 | No.421 しろくろチョコレート |
ユーザー |
![]() |
提出日時 | 2020-07-31 20:38:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,859 bytes |
コンパイル時間 | 1,985 ms |
コンパイル使用メモリ | 195,664 KB |
最終ジャッジ日時 | 2025-01-12 08:49:24 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 61 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); ++i)#define srep(i,s,t) for (int i = s; i < t; ++i)#define drep(i,n) for(int i = (n)-1; i >= 0; --i)using namespace std;typedef long long int ll;typedef pair<int,int> P;#define yn {puts("Yes");}else{puts("No");}#define MAX_N 5005int n;vector<int> G[MAX_N];int match[MAX_N];bool used[MAX_N];void add_edge(int u, int v){G[u].push_back(v);G[v].push_back(u);}bool dfs(int v){used[v] = true;for(int i = 0; i < G[v].size(); i++){int u = G[v][i], w = match[u];if(w < 0 || !used[w] && dfs(w)){match[v] = u;match[u] = v;return true;}}return false;}int bipartite_matching(){int res = 0;memset(match, -1, sizeof(match));for(int v = 0; v < n; v++){if(match[v] < 0){memset(used, 0, sizeof(used));if(dfs(v)){res++;}}}return res;}int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, -1, 0, 1};int main() {int h, w;cin >> h >> w;string s[h];rep(i,h) cin >> s[i];int cntb = 0, cntw = 0;rep(i,h){rep(j,w){if(s[i][j] == 'b') cntb++;if(s[i][j] == 'w'){cntw++;rep(k,4){int nx = i + dx[k];int ny = j + dy[k];if(nx < 0 || h <= nx || ny < 0 || w <= ny) continue;if(s[nx][ny] != 'b') continue;add_edge(i*w+j, nx*w+ny);}}}}int ans = 0;int tmp = bipartite_matching();ans += tmp * 100;cntb -= tmp;cntw -= tmp;ans += min(cntb,cntw) * 10;ans += cntb + cntw - min(cntb,cntw)*2;cout << ans << endl;return 0;}