結果
問題 | No.348 カゴメカゴメ |
ユーザー |
![]() |
提出日時 | 2016-02-26 23:29:56 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,897 bytes |
コンパイル時間 | 1,358 ms |
コンパイル使用メモリ | 165,496 KB |
実行使用メモリ | 74,936 KB |
最終ジャッジ日時 | 2024-09-23 02:19:24 |
合計ジャッジ時間 | 4,476 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 WA * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef vector<int> vi;typedef vector<ll> vl;typedef complex<double> P;typedef pair<int,int> pii;#define REP(i,n) for(ll i=0;i<n;++i)#define REPR(i,n) for(ll i=1;i<n;++i)#define FOR(i,a,b) for(ll i=a;i<b;++i)#define DEBUG(x) cout<<#x<<": "<<x<<endl#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl#define ALL(a) (a).begin(),(a).end()#define MOD (ll)(1e9+7)#define ADD(a,b) a=((a)+(b))%MOD#define FIX(a) ((a)%MOD+MOD)%MODint n,m;int mp[1252][1252];int po[1252][1252];int vx[8] = {1,0,-1,0,1,1,-1,-1};int vy[8] = {0,1,0,-1,1,-1,-1,1};int dfs(int a,int b,int id){if(a<0 || a>=n || b<0 || b>=m)return 0;if(mp[a][b] >= 0)return 0;mp[a][b] = id;int res = 1;REP(i,8){res += dfs(a+vx[i],b+vy[i],id);}return res;}void dfs2(int a,int b,int par){if(a<0 || a>=n || b<0 || b>=m)return;if(mp[a][b] == -1)return;if(mp[a][b] > 0){po[a][b] = par;if(mp[a][b]!=par)return;}mp[a][b] = -1;REP(i,4) dfs2(a+vx[i],b+vy[i],par);}struct node{int val;vector<node*> ch;node(int v):val(v){ch = vector<node*>();}void addch(node* n){ch.push_back(n);}};node* yey[125252];// first: 直前を使った状態を含むmax// second: 直前を使ってない状態のmaxpii dfs3(node* a){pii ret;int cnt = a->ch.size();pii sum;REP(i,cnt){pii rec = dfs3(a->ch[i]);sum.first += rec.first;sum.second += rec.second;}ret.first = a->val + sum.second;ret.second = max(sum.first, sum.second);return ret;}int main(){cin>>n>>m;n+=2;m+=2;REP(i,n){string s;if(i==0 || i==n-1){s = string(m,'.');}else{cin>>s;s = '.' + s + '.';}REP(j,m){mp[i][j] = (s[j]=='x'?-1:0);}}// groupingint wawa[125252];int iter = 1;REP(i,n)REP(j,m){if(mp[i][j]>=0)continue;wawa[iter] = dfs(i,j,iter);iter++;}iter--;// iter個の輪っか// 被覆しながら木構造の形成int left=0, top=0, right=n-1, bottom=m-1;int root = 125222;yey[root] = new node(0);dfs2(0,0,root);while(true){bool flag = false;int nl,nt,nr,nb;nl=right;nt=bottom;nr=left;nb=top;FOR(i,left,right+1)FOR(j,top,bottom+1){if(mp[i][j]<=0)continue;nl=min<int>(nl,i);nr=max<int>(nr,i);nt=min<int>(nt,j);nb=min<int>(nb,j);int id = mp[i][j];yey[id] = new node(wawa[id]);yey[po[i][j]]->addch(yey[id]);dfs2(i,j,id);flag = true;}if(!flag)break;left=nl;right=nr;top=nt;bottom=nb;}// 終わった~~~~~int res = 0;REP(i,(yey[root]->ch).size()){node* to = (yey[root]->ch)[i];pii x = dfs3(to);res += max(x.first,x.second);}cout<<res<<endl;return 0;}