結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
 はまやんはまやん
|
| 提出日時 | 2017-05-09 12:59:56 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 8,179 bytes |
| コンパイル時間 | 2,273 ms |
| コンパイル使用メモリ | 186,428 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-09-23 07:15:06 |
| 合計ジャッジ時間 | 3,896 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 3 ms
6,940 KB |
| testcase_02 | AC | 3 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 2 ms
6,944 KB |
| testcase_05 | AC | 2 ms
6,944 KB |
| testcase_06 | AC | 2 ms
6,940 KB |
| testcase_07 | AC | 3 ms
6,944 KB |
| testcase_08 | AC | 2 ms
6,940 KB |
| testcase_09 | AC | 3 ms
6,940 KB |
| testcase_10 | AC | 2 ms
6,940 KB |
| testcase_11 | AC | 3 ms
6,944 KB |
| testcase_12 | AC | 2 ms
6,940 KB |
| testcase_13 | AC | 2 ms
6,944 KB |
| testcase_14 | AC | 2 ms
6,944 KB |
| testcase_15 | AC | 2 ms
6,944 KB |
| testcase_16 | AC | 4 ms
6,944 KB |
| testcase_17 | AC | 4 ms
6,944 KB |
| testcase_18 | AC | 5 ms
6,944 KB |
| testcase_19 | AC | 2 ms
6,944 KB |
| testcase_20 | AC | 3 ms
6,940 KB |
| testcase_21 | AC | 4 ms
6,940 KB |
| testcase_22 | AC | 3 ms
6,940 KB |
| testcase_23 | AC | 2 ms
6,944 KB |
| testcase_24 | AC | 2 ms
6,940 KB |
| testcase_25 | AC | 2 ms
6,944 KB |
| testcase_26 | AC | 2 ms
6,944 KB |
| testcase_27 | AC | 2 ms
6,940 KB |
| testcase_28 | AC | 3 ms
6,940 KB |
| testcase_29 | AC | 3 ms
6,944 KB |
| testcase_30 | AC | 2 ms
6,944 KB |
| testcase_31 | AC | 4 ms
6,940 KB |
| testcase_32 | AC | 3 ms
6,944 KB |
| testcase_33 | AC | 3 ms
6,944 KB |
| testcase_34 | AC | 2 ms
6,940 KB |
| testcase_35 | AC | 2 ms
6,944 KB |
| testcase_36 | AC | 2 ms
6,940 KB |
| testcase_37 | AC | 4 ms
6,944 KB |
| testcase_38 | AC | 5 ms
6,944 KB |
| testcase_39 | AC | 3 ms
6,940 KB |
| testcase_40 | AC | 3 ms
6,940 KB |
| testcase_41 | AC | 2 ms
6,944 KB |
| testcase_42 | AC | 2 ms
6,944 KB |
| testcase_43 | AC | 3 ms
6,944 KB |
| testcase_44 | AC | 4 ms
6,944 KB |
| testcase_45 | AC | 2 ms
6,944 KB |
| testcase_46 | AC | 2 ms
6,940 KB |
| testcase_47 | AC | 3 ms
6,940 KB |
| testcase_48 | AC | 4 ms
6,940 KB |
| testcase_49 | AC | 2 ms
6,944 KB |
| testcase_50 | AC | 2 ms
6,944 KB |
| testcase_51 | AC | 4 ms
6,944 KB |
| testcase_52 | AC | 2 ms
6,944 KB |
| testcase_53 | AC | 2 ms
6,940 KB |
| testcase_54 | AC | 3 ms
6,940 KB |
| testcase_55 | AC | 2 ms
6,948 KB |
| testcase_56 | AC | 2 ms
6,940 KB |
| testcase_57 | AC | 2 ms
6,944 KB |
| testcase_58 | AC | 3 ms
6,944 KB |
| testcase_59 | AC | 3 ms
6,940 KB |
| testcase_60 | AC | 6 ms
6,940 KB |
| testcase_61 | AC | 5 ms
6,940 KB |
| testcase_62 | AC | 2 ms
6,940 KB |
| testcase_63 | AC | 2 ms
6,944 KB |
| testcase_64 | AC | 2 ms
6,940 KB |
ソースコード
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<class V> struct MaxFlow {
struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} };
int MV; vector<vector<edge>> E; vector<int> itr, lev;
MaxFlow() {} MaxFlow(int n) { init(n); }
void init(int n) { MV = n; itr = vector<int>(MV), lev = vector<int>(MV); E = vector<vector<edge>>(MV); }
void add_edge(int x, int y, V cap, bool undir = false) { E[x].push_back(edge(y, (int)E[y].size(), cap));
E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0)); }
void bfs(int cur) { rep(i, 0, MV) lev[i] = -1; queue<int> q; lev[cur] = 0; q.push(cur);
while (q.size()) { int v = q.front(); q.pop();
for(auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to); } }
V dfs(int from, int to, V cf) { if (from == to) return cf;
for (; itr[from]<E[from].size(); itr[from]++) {
edge* e = &E[from][itr[from]]; if (e->cap>0 && lev[from]<lev[e->to]) {
V f = dfs(e->to, to, min(cf, e->cap));
if (f>0) { e->cap -= f; E[e->to][e->reve].cap += f; return f; }
} } return 0; }
V maxflow(int from, int to) { V fl = 0, tf;
while (1) { bfs(from); if (lev[to]<0) return fl;
rep(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;
}
}
};
struct BipartiteMatching {
int N, M; MaxFlow<int> mf;
BipartiteMatching(int n, int m) : N(n), M(m) { mf.init(n + m + 2); }
void add_edge(int a, int b) { mf.add_edge(a, N + b, 1); }
int match() {
rep(a, 0, N) mf.add_edge(N + M, a, 1);
rep(b, 0, M) mf.add_edge(N + b, N + M + 1, 1);
return mf.maxflow(N + M, N + M + 1); }
int whois(int a) { // マッチング相手を返す(無いなら-1)
for (auto e : mf.E[a]) if (e.cap == 0) return e.to - N;
return -1;
}
};
//---------------------------------------------------------------------------------------------------
int H, W;
string S[50];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> H >> W;
rep(i, 0, H) cin >> S[i];
vector<int> b, w;
rep(y, 0, H) rep(x, 0, W) {
if (S[y][x] == 'b') b.push_back(y * W + x);
if (S[y][x] == 'w') w.push_back(y * W + x);
}
sort(b.begin(), b.end());
sort(w.begin(), w.end());
BipartiteMatching bm(b.size(), w.size());
rep(y, 0, H) rep(x, 0, W) if(S[y][x] == 'b'){
rep(i, 0, 4) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || W <= xx) continue;
if (yy < 0 || H <= yy) continue;
if (S[yy][xx] != 'w') continue;
int bb = lower_bound(b.begin(), b.end(), y * W + x) - b.begin();
int ww = lower_bound(w.begin(), w.end(), yy * W + xx) - w.begin();
bm.add_edge(bb, ww);
}
}
int p100 = bm.match();
int rb = b.size() - p100;
int rw = w.size() - p100;
int p10 = min(rb, rw);
int ans = 100 * p100 + 10 * p10 + (b.size() - p100 - p10) + (w.size() - p100 - p10);
cout << ans << endl;
}
/* `
`` `
. ` .g,`
Welcome To My Coding Space! .MMe `(F(#~ `.J,
`.M/7b. dD.N; (#=#:
`` db (m.#` Wl(@ jF `
`` ` ` ` ..+kMMN;_(Y> `(TD d$..gHN_
` `` ...... ` ` ` `..gMB61+1+dK `- `. .TM@^(d%
`` `` ..JggHHMMHHYYTHMMMNmgJ.. .kB6z?1+z1+<dD ..` . ``.` `.V'
``..+HMBYC1?1+???=?====????1vTHMNe+1+dMB"BMMM% .`je. `.. ..+@`
`..gM9C1+?==??==?==?=?===??=??=?1?zTMNeJTHg..``...`.,S._`.` d$ `
` ` .(kBY1+==????=?=??=?=??=???=?=?=?=????+zTMm+?TMm.. ` d[ .``.M}
`.(M9++?=????==???=?=??=?=?=?=?=?=?=?===?==1+7Mmx?MN,``..._^`.. (F `
` ` ` ` ` ` (M8++z11==?==??==??=?==?=?=?==??=??=??==??==?=+7Mm<dNg, ` .`.. (#! `
` ` ..(JgH@MMMMMMB1+=??=??=?????==11??1=1?1?=1+=11?1==?=1=??=??11+WNJdMt .``.` J#! `
.(HHYYC?1+??z>+H8+=??=?=?=???=?=?=z1&z1?==?1<dNs111?==1ux?==?=?==1zdNcW% ..`. J#~`
`.WNx<?1?==1=zdMD+=?==?===?=?==?===<dNNx1z??==+WMN+g&&&xdMk1??=1===???MN}`.`.`. J#` `
` ?MNc1=1?z?jH8+==?=?==??=jQ21=?=?(M$?WNx<1=zudMMMszOCvTHMmx+?1?z+1?zd#:..`.`. J@ `
`` .M81==?==>dM<??===?=?=?+dNy+?=?jM@ ` ?WNe+zO>dNcHmJ1+1JMMR1?z??Ne1<d#~.`..`. dF
(M3+1+?==?jMD+=?z1&&?v1+jMMb+=?1d#!`..``?HNx+?+HR ?Mm+1<dMMp?==<dNc<d#_.`..`.`dF `
,MHmax111=<dNC?=?=(M#ugH9M#W#6+?(M'`.`.... ?WNe<dM: .TNm<dN?Nm<=zzMR+M@` .``.. dF `
` `` _CM$+??1d#<==?=>dM9+?(MF(MI+jMf .`.``.`.. (TNaHr`.`.TNmN:(MR+?zMK(M$` `.`.``dF `
J#<=1<jME+1?=1d9Mn1<jN! qN(d@_.`..`.`.`.```-7Y5.....,TB! (MmJ+MH(M: ...`.`.d$`
` .M$iggWWMR+1?<dDjMNxjMB .NgN``..``.`.``....`.d#Y"""YWNg. .WNxW#J@ .`.`.``.H: `
_Y""! .M$jm+?1zd#TNzM}.. ?M% .`..`.`..``.`.. .+NMNg,.?Mm._ ?NMNM$ ..`..``.# `
.HPj#z=?<d#_WM#:.JgHH6 . `.`.`..``.`.`jMMF`.MMN..TN, ?@jM}`..`.`.`JD `
` ` dbjMI?=+MF`.7XME^_.--,. ..`.``.`..`.`.M#XNgjNdMR. ?N-. (#~``.``.. d%
` d#<WR1z(Mt` (#' (MMBTHNe.`..`..`.`.` .M#UMMMM#W#_. zN. dF`.`...`..H} `
?MO(N+?jM:`.M!`.M9N+.-MMR `..`..`.`.`_?MmTMMMwM#~...H: .H}`..`..` (#`
` ` ` WNJMR<dN_ JB dNwMMMMNdM[`.`.`.`.`.. ,TNNggMB! .` ~ `(M `.`.``. dF
`.MdMNoW@ `JP `(MKdMMNMdM}`.`..`.`.`.... .??!`.`.`..`..dD .`....`.W'
?MMMMMP `(R`..?MmyUWQMB ..`..`.`.`..`..`..`.`.`_`-.gM#!.`.``.``.@
` `` _7NTMN.`.H/`. ,TMMB"! .``.`.`..`.``.``.`..`.`. .,NIdb` .`..` j$
` Wm.M;`._!..`.`...`_`...``.. ...(+ga,`.....``(NjMr`..`... .#:
.MpdN_.`. ``.``.`..`..(-JggkWY9YC<>;?Wp .``.` J#>dN, ..``.`dF`
`_UmMn .`..`..`..`. JMYT1<;;;>>>>>;>>?Wo ..`. dK1=dN,`..``.MN+
.dMMe .`.``.`.`.` d#<;>>>>;>>>>;>>>>(N,`.. -MK1llvWm. JM?Mp. ` `
` .M9+?Me`.`..`.`.`` JN(>;>>;>>;>>>;>>><db` (kH5lllllzXMm.-NNszWm ` `
` (#1+???Hm, ..`..`..`(N:>>>>>;>>>>>;>>><d@_.JNZIlllllllzvTWB6zlJMp `
` `` j@1+==?1zvHm.`...`....Hc<>>>>>>>>>>>>><(W$(M8TIllllllllllllllllzvMo ` ` `
(#1?==1?===z?TNa,.` `` (Ne<<>>>>><;><;jgMMY1HK1lllllllllllllllllllJMp `
.Ne&g&x1=?=?==?1zTHNmJ-...dNgJ++++&ggMH9=~ .M9Izlllllllllllllllllll1WF `
` _???MK<=??=??1z?(MM@!d#M#Y""""=<!!~``` .d8Illllllll=lll=lllllllzudY ` `
` dH<?+uev?=1uMM^ d@vN&.`...`.`.`.-JH91zzl=llllllllllll=lzllzd#' ` `
,MNMBHNIvjdB(D ` d#=zTNm.....JgHM9Izlllludk=zl=ll=llllllvug#^
` ` `.MmgM=+M$ ` d#zzO1vUUUU9TI=lllzzO1dKT#zOlllll=llll=dM=
` `(Y^ JBdr ` dNmxzIlllllllllllz1ug#= .My1llllllllllzdD `
` j@1dR ``(#~THaxl=lzzlzzzugW"!` ``,Nzlzz=lllllzd#: `
` ` .#z=d# ``(#_` .7THWQkWHB"^ ` ` ` ?NsIzzlll=ljM\
` `` (M6zldN_` .M| ` `` ` .WezllzllzH% `` `
` ` .+#Czl=dM;` dR ` 4m+zll1dD
` `.d@1llzvdMb ,# ` ` ?Wmxzdf */