結果
問題 | No.2509 Beam Shateki |
ユーザー |
![]() |
提出日時 | 2023-10-23 16:08:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 2,264 bytes |
コンパイル時間 | 1,013 ms |
コンパイル使用メモリ | 86,216 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 10:34:12 |
合計ジャッジ時間 | 5,565 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <string> #include <set> #include <map> #include <vector> #include <queue> #define ll long long #define db double using namespace std; ll tt,a[105][105],h,w; pair<ll,ll> pr[1005]; bool vis[105][105]; ll getval(ll ty, ll val) { ll res = 0; if (ty == 1) { for (ll i = 1;i <= w;i++) { if (!vis[val][i]) { vis[val][i] = 1; res += a[val][i]; } } } if (ty == 2) { for (ll i = 1;i <= h;i++) { if (!vis[i][val]) { vis[i][val] = 1; res += a[i][val]; } } } if (ty == 3) { for (ll i = 1;i <= h;i++) { if ((val - i > w) || (val - i < 1)) { continue; } if (!vis[i][val - i]) { vis[i][val - i] = 1; res += a[i][val - i]; } } } if (ty == 4) { for (ll i = 1;i <= h;i++) { if ((i - val > w) || (i - val < 1)) { continue; } if (!vis[i][i - val]) { vis[i][i - val] = 1; res += a[i][i - val]; } } } return res; } void clr(ll ty,ll val) { if (ty == 1) { for (ll i = 1;i <= w;i++) { vis[val][i] = 0; } } if (ty == 2) { for (ll i = 1;i <= h;i++) { vis[i][val] = 0; } } if (ty == 3) { for (ll i = 1;i <= h;i++) { if ((val - i > w) || (val - i < 1)) { continue; } vis[i][val - i] = 0; } } if (ty == 4) { for (ll i = 1;i <= h;i++) { if ((i - val > w) || (i - val < 1)) { continue; } vis[i][i - val] = 0; } } } void solve() { scanf("%lld%lld",&h,&w); for (ll i = 1;i <= h;i++) { for (ll j = 1;j <= w;j++) { scanf("%lld",&a[i][j]); } } ll tot = 0; for (ll i = 1;i <= h;i++) { pr[++tot] = make_pair(1ll,i); } for (ll i = 1;i <= w;i++) { pr[++tot] = make_pair(2ll,i); } for (ll i = 2;i <= h + w;i++) { pr[++tot] = make_pair(3ll,i); } for (ll i = 1 - w;i <= h - 1;i++) { pr[++tot] = make_pair(4ll,i); } memset(vis,0,sizeof(vis)); ll ans = 0; for (ll i = 1;i <= tot;i++) { for (ll j = i + 1;j <= tot;j++) { ll sum = 0; sum += getval(pr[i].first,pr[i].second); sum += getval(pr[j].first,pr[j].second); ans = max(ans,sum); clr(pr[i].first,pr[i].second); clr(pr[j].first,pr[j].second); } } printf("%lld\n",ans); } int main() { tt = 1; while(tt) { solve(); tt--; } return 0; }