結果
問題 | No.2509 Beam Shateki |
ユーザー |
|
提出日時 | 2023-10-20 23:04:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,578 bytes |
コンパイル時間 | 2,314 ms |
コンパイル使用メモリ | 184,776 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 21:48:06 |
合計ジャッジ時間 | 3,839 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){int h,w;cin >> h >> w;vector<vector<int>> A(h,vector<int>(w));vector<int> R(h,0); // 行合計vector<int> C(w,0); // 列合計vector<int> S(h+w-1,0); // 斜め合計(右上から左下、添字の和が一定)map<int,int> M; //斜め合計(左上から右下、添字の差(行番号-列番号が一定))for(int i=0;i<h;i++){for(int j=0;j<w;j++){cin >> A[i][j];int& a=A[i][j];R[i]+=a;C[j]+=a;S[i+j]+=a;M[i-j]+=a;}}int ans=0;//平行方向にチェック//行for(int i=0;i<h;i++){//ビーム1回の場合if(R[i]>ans)ans=R[i];for(int j=i+1;j<h;j++){int s=R[i]+R[j];if(s>ans)ans=s;}}//列番号が一定for(int i=0;i<w;i++){//ビーム1回の場合if(C[i]>ans)ans=C[i];for(int j=i+1;j<w;j++){int s=C[i]+C[j];if(s>ans)ans=s;}}//斜め(添字の和が一定)for(int i=0;i<h+w-1;i++){//ビーム1回の場合if(S[i]>ans)ans=S[i];for(int j=i+1;j<h+w-1;j++){int s=S[i]+S[j];if(s>ans)ans=s;}}//斜め(添字の差が一定)for(int i=1-w;i<h;i++){//ビーム1回の場合if(M[i]>ans)ans=M[i];for(int j=i+1;j<h;j++){int s=M[i]+M[j];if(s>ans)ans=s;}}//タテ・ヨコfor(int i=0;i<h;i++){for(int j=0;j<w;j++){int s=R[i]+C[j]-A[i][j]; //交差している箱は引くif(s>ans)ans=s;}}//ヨコ・ナナメ(添字の和が一定)for(int i=0;i<h;i++){for(int j=0;j<h+w-1;j++){int x=j-i; //交点int s=R[i]+S[j];if(0<=x && x<w)s-=A[i][x];if(s>ans)ans=s;}}//ヨコ・ナナメ(添字の差が一定)for(int i=0;i<h;i++){for(int j=1-w;j<h;j++){int x=i-j; //交点int s=R[i]+M[j];if(0<=x && x<w)s-=A[i][x];if(s>ans)ans=s;}}//タテ・ナナメ(添字の和が一定)for(int i=0;i<w;i++){for(int j=0;j<h+w-1;j++){int y=j-i; //交点int s=C[i]+S[j];if(0<=y && y<h)s-=A[y][i];if(s>ans)ans=s;}}//タテ・ナナメ(添字の差が一定)for(int i=0;i<w;i++){for(int j=1-w;j<h;j++){int y=j+i; //交点int s=C[i]+M[j];if(0<=y && y<h)s-=A[y][i];if(s>ans)ans=s;}}//ナナメ直交for(int i=0;i<h+w-1;i++){for(int j=1-w;j<h;j++){int s=S[i]+M[j];if((i+j)%2==0){//y+x=i, y-x=jint y=(i+j)/2;int x=(i-j)/2;//x+yが偶数ならx-yも偶数if(0<=y&&y<h&&0<=x&&x<w){s-=A[y][x];}}if(s>ans)ans=s;}}cout << ans << endl;return 0;}