結果
問題 | No.2509 Beam Shateki |
ユーザー | Nzt3 |
提出日時 | 2023-10-20 23:00:48 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,846 ms / 2,000 ms |
コード長 | 4,561 bytes |
コンパイル時間 | 3,411 ms |
コンパイル使用メモリ | 275,092 KB |
実行使用メモリ | 41,752 KB |
最終ジャッジ日時 | 2023-10-20 23:01:48 |
合計ジャッジ時間 | 58,089 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
4,348 KB |
testcase_01 | AC | 4 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 443 ms
13,308 KB |
testcase_04 | AC | 410 ms
13,308 KB |
testcase_05 | AC | 409 ms
13,308 KB |
testcase_06 | AC | 441 ms
13,308 KB |
testcase_07 | AC | 407 ms
13,308 KB |
testcase_08 | AC | 409 ms
13,308 KB |
testcase_09 | AC | 414 ms
13,308 KB |
testcase_10 | AC | 408 ms
13,308 KB |
testcase_11 | AC | 409 ms
13,308 KB |
testcase_12 | AC | 417 ms
13,308 KB |
testcase_13 | AC | 1,788 ms
41,752 KB |
testcase_14 | AC | 1,781 ms
41,752 KB |
testcase_15 | AC | 1,846 ms
41,752 KB |
testcase_16 | AC | 1,795 ms
41,752 KB |
testcase_17 | AC | 1,790 ms
41,752 KB |
testcase_18 | AC | 1,822 ms
41,752 KB |
testcase_19 | AC | 1,788 ms
41,752 KB |
testcase_20 | AC | 1,824 ms
41,752 KB |
testcase_21 | AC | 1,788 ms
41,752 KB |
testcase_22 | AC | 1,788 ms
41,752 KB |
testcase_23 | AC | 1,821 ms
41,752 KB |
testcase_24 | AC | 1,794 ms
41,752 KB |
testcase_25 | AC | 1,788 ms
41,752 KB |
testcase_26 | AC | 1,827 ms
41,752 KB |
testcase_27 | AC | 1,785 ms
41,752 KB |
testcase_28 | AC | 1,823 ms
41,752 KB |
testcase_29 | AC | 1,797 ms
41,752 KB |
testcase_30 | AC | 1,795 ms
41,752 KB |
testcase_31 | AC | 1,821 ms
41,752 KB |
testcase_32 | AC | 1,802 ms
41,752 KB |
testcase_33 | AC | 101 ms
6,208 KB |
testcase_34 | AC | 639 ms
18,096 KB |
testcase_35 | AC | 1,085 ms
27,444 KB |
testcase_36 | AC | 339 ms
10,724 KB |
testcase_37 | AC | 132 ms
4,348 KB |
testcase_38 | AC | 362 ms
11,196 KB |
testcase_39 | AC | 345 ms
10,308 KB |
testcase_40 | AC | 717 ms
19,984 KB |
testcase_41 | AC | 22 ms
4,348 KB |
testcase_42 | AC | 431 ms
12,148 KB |
testcase_43 | AC | 1,256 ms
31,036 KB |
testcase_44 | AC | 1,477 ms
34,352 KB |
testcase_45 | AC | 309 ms
10,472 KB |
testcase_46 | AC | 532 ms
13,124 KB |
testcase_47 | AC | 1,434 ms
34,404 KB |
testcase_48 | AC | 579 ms
16,084 KB |
testcase_49 | AC | 831 ms
21,484 KB |
testcase_50 | AC | 921 ms
24,336 KB |
testcase_51 | AC | 106 ms
5,716 KB |
testcase_52 | AC | 695 ms
18,592 KB |
testcase_53 | AC | 6 ms
4,348 KB |
testcase_54 | AC | 5 ms
4,348 KB |
testcase_55 | AC | 6 ms
4,348 KB |
testcase_56 | AC | 7 ms
4,348 KB |
testcase_57 | AC | 7 ms
4,348 KB |
testcase_58 | AC | 7 ms
4,348 KB |
testcase_59 | AC | 6 ms
4,348 KB |
testcase_60 | AC | 6 ms
4,348 KB |
testcase_61 | AC | 7 ms
4,348 KB |
testcase_62 | AC | 6 ms
4,348 KB |
testcase_63 | AC | 7 ms
4,348 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; void ch_ans(const vector<array<int,9>>& V1,const vector<array<int,9>>& V2,int v1d,int v2d,map<array<array<int,4>,2>,int>& ng,int& ans){ for(int i=0;i<V1.size();i++){ for(int dx1=-1;dx1<=1;dx1++){ for(int dy1=-1;dy1<=1;dy1++){ array<int,4>d1={v1d,i,dx1,dy1}; for(int j=0;j<V2.size();j++){ for(int dx2=-1;dx2<=1;dx2++){ for(int dy2=-1;dy2<=1;dy2++){ array<int,4>d2={v2d,j,dx2,dy2}; if(d1==d2)continue; int now=V1[i][(dx1+1)*3+(dy1+1)]+V2[j][(dx2+1)*3+(dy2+1)]; if(ng.contains({d1,d2})){ now-=ng[{d1,d2}]; } if(now>ans){ ans=now; } ans=max(ans,now); } } } } } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H,W; cin>>H>>W; vector A(H,vector(W,0)); for(int i=0;i<H;i++){ for(int j=0;j<W;j++)cin>>A[i][j]; } vector<array<int,9>> H0(W+2),H1(W+2),W0(H+2),W1(H+2); for(int i=0;i<W+2;i++){ fill(H0[i].begin(),H0[i].end(),0); fill(H1[i].begin(),H1[i].end(),0); } for(int i=0;i<H+2;i++){ fill(W0[i].begin(),W0[i].end(),0); fill(W1[i].begin(),W1[i].end(),0); } auto bound_ok =[&](int x,int y){ return x>=0&&x<H&&y>=0&&y<W; }; for(int i=0;i<W+2;i++){ for(int dx=-1;dx<=1;dx++){ for(int dy=-1;dy<=1;dy++){ if(dx==0&&dy==0)continue; int t=(dx+1)*3+(dy+1); int x=-1,y=i-1; x+=dx,y+=dy; while(1){ if(!bound_ok(x,y))break; H0[i][t]+=A[x][y]; x+=dx,y+=dy; } } } } for(int i=0;i<W+2;i++){ for(int dx=-1;dx<=1;dx++){ for(int dy=-1;dy<=1;dy++){ if(dx==0&&dy==0)continue; int t=(dx+1)*3+(dy+1); int x=H,y=i-1; x+=dx,y+=dy; while(1){ if(!bound_ok(x,y))break; H1[i][t]+=A[x][y]; x+=dx,y+=dy; } } } } for(int i=0;i<H+2;i++){ for(int dx=-1;dx<=1;dx++){ for(int dy=-1;dy<=1;dy++){ if(dx==0&&dy==0)continue; int t=(dx+1)*3+(dy+1); int x=i-1,y=-1; x+=dx,y+=dy; while(1){ if(!bound_ok(x,y))break; W0[i][t]+=A[x][y]; x+=dx,y+=dy; } } } } for(int i=0;i<H+2;i++){ for(int dx=-1;dx<=1;dx++){ for(int dy=-1;dy<=1;dy++){ if(dx==0&&dy==0)continue; int t=(dx+1)*3+(dy+1); int x=i-1,y=W; x+=dx,y+=dy; while(1){ if(!bound_ok(x,y))break; W1[i][t]+=A[x][y]; x+=dx,y+=dy; } } } } map<array<array<int,4>,2>,int>ng; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ vector<array<int,4>>d; for(int dx=-1;dx<=1;dx++){ for(int dy=-1;dy<=1;dy++){ if(dy==0&&dx==0)continue; int x=i,y=j; while(bound_ok(x,y)){ x-=dx,y-=dy; } if(x==-1){ d.push_back({0,y+1,dx,dy}); } if(x==H){ d.push_back({1,y+1,dx,dy}); } if(y==-1){ d.push_back({2,x+1,dx,dy}); } if(y==W){ d.push_back({3,x+1,dx,dy}); } } } for(auto d1:d){ for(auto d2:d){ ng[{d1,d2}]=A[i][j]; if(d1[2]==d2[2]&&d1[3]==d2[3]||d1[2]==-d2[2]&&d1[3]==-d2[3]){ switch(d1[0]){ case 0:ng[{d1,d2}]=H0[d1[1]][(d1[2]+1)*3+(d1[3]+1)];break; case 1:ng[{d1,d2}]=H1[d1[1]][(d1[2]+1)*3+(d1[3]+1)];break; case 2:ng[{d1,d2}]=W0[d1[1]][(d1[2]+1)*3+(d1[3]+1)];break; case 3:ng[{d1,d2}]=W1[d1[1]][(d1[2]+1)*3+(d1[3]+1)];break; } } } } } } int ans=0; for(auto i:H0){ for(auto j:i)ans=max(ans,j); } for(auto i:H1){ for(auto j:i)ans=max(ans,j); } for(auto i:W0){ for(auto j:i)ans=max(ans,j); } for(auto i:W1){ for(auto j:i)ans=max(ans,j); } ch_ans(H0,H0,0,0,ng,ans); ch_ans(H0,H1,0,1,ng,ans); ch_ans(H0,W0,0,2,ng,ans); ch_ans(H0,W1,0,3,ng,ans); ch_ans(H1,H0,1,0,ng,ans); ch_ans(H1,H1,1,1,ng,ans); ch_ans(H1,W0,1,2,ng,ans); ch_ans(H1,W1,1,3,ng,ans); ch_ans(W0,H0,2,0,ng,ans); ch_ans(W0,H1,2,1,ng,ans); ch_ans(W0,W0,2,2,ng,ans); ch_ans(W0,W1,2,3,ng,ans); ch_ans(W1,H0,3,0,ng,ans); ch_ans(W1,H1,3,1,ng,ans); ch_ans(W1,W0,3,2,ng,ans); ch_ans(W1,W1,3,3,ng,ans); cout<<ans<<'\n'; }