結果
問題 | No.2509 Beam Shateki |
ユーザー |
|
提出日時 | 2023-10-20 22:05:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 2,668 bytes |
コンパイル時間 | 1,002 ms |
コンパイル使用メモリ | 97,020 KB |
最終ジャッジ日時 | 2025-02-17 09:30:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<set>#include<atcoder/modint>using namespace std;using namespace atcoder;using ll=long long;using mint=modint998244353;#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}const int dx[]={-1,0,1},dy[]={-1,0,1};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int H,W;cin>>H>>W;vector A(H+2,vector<ll>(W+2));for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)cin>>A[i][j];vector<pair<int,int>>vp;for(int i=0;i<=W;i++)vp.push_back(make_pair(0,i));for(int i=0;i<=H;i++)vp.push_back(make_pair(i,W+1));for(int i=W+1;i>=1;i--)vp.push_back(make_pair(H+1,i));for(int i=H+1;i>=1;i--)vp.push_back(make_pair(i,0));int L=vp.size();vector D(L,vector(3,vector<ll>(3)));for(int i=0;i<L-1;i++){for(int k=0;k<3;k++)for(int l=0;l<3;l++){if(k==1&&l==1)continue;ll cnt=0;int axi=vp[i].first,ayi=vp[i].second;while(axi>=0&&axi<=H+1&&ayi>=0&&ayi<=W+1){cnt+=A[axi][ayi];axi+=dx[k];ayi+=dy[l];}D[i][k][l]=cnt;}}ll ans=0;vector flag(H+2,vector<bool>(W+2));for(int i=0;i<L-1;i++){for(int j=i+1;j<L;j++){for(int a=0;a<3;a++)for(int b=0;b<3;b++)for(int c=0;c<3;c++)for(int d=0;d<3;d++){if((a==1&&b==1)||(c==1&&d==1))continue;ll cnt=D[i][a][b]+D[j][c][d];if(cnt<ans)continue;int axi=vp[i].first,ayi=vp[i].second;int axj=vp[j].first,ayj=vp[j].second;set<pair<int,int>>se;while(axi>=0&&axi<=H+1&&ayi>=0&&ayi<=W+1){flag[axi][ayi]=true;axi+=dx[a];ayi+=dy[b];}while(axj>=0&&axj<=H+1&&ayj>=0&&ayj<=W+1){if(flag[axj][ayj]){cnt-=A[axj][ayj];}axj+=dx[c];ayj+=dy[d];}if(axi-dx[a]==vp[j].first&&ayi-dy[b]==vp[j].second)continue;chmax(ans,cnt);while(axi-dx[a]>=0&&axi-dx[a]<=H+1&&ayi-dy[b]>=0&&ayi-dy[b]<=W+1){axi-=dx[a];ayi-=dy[b];flag[axi][ayi]=false;}}}}cout<<ans<<"\n";}