結果
問題 | No.2328 Build Walls |
ユーザー | Haa |
提出日時 | 2023-05-28 15:03:40 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,240 bytes |
コンパイル時間 | 4,446 ms |
コンパイル使用メモリ | 248,536 KB |
実行使用メモリ | 727,308 KB |
最終ジャッジ日時 | 2023-08-27 11:18:19 |
合計ジャッジ時間 | 15,555 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | AC | 190 ms
151,984 KB |
testcase_14 | AC | 232 ms
173,996 KB |
testcase_15 | AC | 170 ms
122,452 KB |
testcase_16 | AC | 33 ms
24,304 KB |
testcase_17 | AC | 174 ms
118,836 KB |
testcase_18 | AC | 6 ms
6,152 KB |
testcase_19 | AC | 22 ms
16,988 KB |
testcase_20 | AC | 18 ms
14,052 KB |
testcase_21 | AC | 95 ms
47,076 KB |
testcase_22 | AC | 373 ms
266,292 KB |
testcase_23 | AC | 838 ms
457,412 KB |
testcase_24 | AC | 764 ms
421,020 KB |
testcase_25 | AC | 828 ms
451,692 KB |
testcase_26 | AC | 546 ms
344,252 KB |
testcase_27 | AC | 616 ms
398,760 KB |
testcase_28 | AC | 141 ms
38,384 KB |
testcase_29 | AC | 716 ms
456,972 KB |
testcase_30 | AC | 342 ms
279,452 KB |
testcase_31 | AC | 305 ms
237,888 KB |
testcase_32 | AC | 597 ms
393,012 KB |
testcase_33 | MLE | - |
testcase_34 | AC | 385 ms
293,220 KB |
testcase_35 | MLE | - |
testcase_36 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; typedef long long int ll; typedef pair<ll,ll> P; typedef vector<ll> VI; typedef vector<VI> VVI; #define REP(i,n) for(int i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() template<typename T> bool chmax(T& x, const T& y){return (x<y)?(x=y,true):false;}; template<typename T> bool chmin(T& x, const T& y){return (x>y)?(x=y,true):false;}; constexpr ll MOD=998244353; constexpr ll INF=2e18; const int dx[8]={1,0,-1,0,1,1,-1,-1}, dy[8]={0,1,0,-1,1,-1,1,-1}; int main(){ int h, w; cin >> h >> w; h-=2; VVI a(h,VI(w)); REP(i,h)REP(j,w) cin >> a[i][j]; mcf_graph<int,ll> g(h*w+2); int s=h*w, t=h*w+1; REP(i,h)REP(j,w){ if(a[i][j]==-1) continue; REP(k,8){ int ti=i+dx[k], tj=j+dy[k]; if(ti<0||ti>=h||tj<0||tj>=w) continue; g.add_edge(i*w+j,ti*w+tj,1,a[i][j]); if(j==0) g.add_edge(s,i*w+j,1,0); else if(j==w-1) g.add_edge(i*w+j,t,1,a[i][j]); } } auto ans=g.flow(s,t,1); if(ans.first==0) cout << -1 << endl; else cout << ans.second << endl; return 0; }