結果
問題 | No.2509 Beam Shateki |
ユーザー |
![]() |
提出日時 | 2023-10-20 22:11:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,877 bytes |
コンパイル時間 | 1,656 ms |
コンパイル使用メモリ | 129,372 KB |
最終ジャッジ日時 | 2025-02-17 09:38:56 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 WA * 1 |
ソースコード
#include <algorithm>#include <iostream>#include <iomanip>#include <limits.h>#include <map>#include <math.h>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <utility>#include <vector>#include <stack>#include <complex>using namespace std;#define rep(i, n) for (ll i = 0; i < n; i++)#define rep1(i, n) for (ll i = 1; i < n + 1; i++)#define rev(i, n) for (ll i = n - 1; i >= 0; i--)#define all(A) A.begin(), A.end()#define itr(A, l, r) A.begin() + l, A.begin() + r#define debug(var) cout << #var << " = " << var << endl;typedef long long ll;template <typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << "(" << p.first << "," << p.second << ")";return os;}template <typename T1, typename T2>istream &operator>>(istream &is, pair<T1, T2> &p){is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &v){for (ll i = 0; i < (ll)v.size(); i++){os << v[i] << (i + 1 != (ll)v.size() ? " " : "");}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &v){for (ll i = 0; i < (ll)v.size(); i++){os << v[i] << endl;}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v){ll n = v.size();ll m = v[0].size();ll p = v[0][0].size();rep(k, p){os << "k = " << k << endl;rep(i, n){rep(j, m){os << v[i][j][k];if (j < m - 1){os << " ";}else{os << endl;}}}}return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v){for (T &in : v)is >> in;return is;}template <typename T, typename S>ostream &operator<<(ostream &os, map<T, S> &mp){for (auto &[key, val] : mp){os << key << ":" << val << " ";}cout << endl;return os;}template <typename T>ostream &operator<<(ostream &os, set<T> st){auto itr = st.begin();for (ll i = 0; i < (ll)st.size(); i++){os << *itr << (i + 1 != (ll)st.size() ? " " : "");itr++;}return os;}template <typename T>ostream &operator<<(ostream &os, multiset<T> st){auto itr = st.begin();for (ll i = 0; i < (ll)st.size(); i++){os << *itr << (i + 1 != (ll)st.size() ? " " : "");itr++;}return os;}template <typename T>ostream &operator<<(ostream &os, queue<T> q){while (q.size()){os << q.front() << " ";q.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, deque<T> q){while (q.size()){os << q.front() << " ";q.pop_front();}return os;}template <typename T>ostream &operator<<(ostream &os, stack<T> st){while (st.size()){os << st.top() << " ";st.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, priority_queue<T> pq){while (pq.size()){os << pq.top() << " ";pq.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, priority_queue<T, vector<T>, greater<T>> mpq){while (mpq.size()){os << mpq.top() << " ";mpq.pop();}return os;}vector<vector<ll>> maze;vector<ll> way;vector<map<ll, ll>> sum(4);map<ll, pair<ll, ll>> lim;vector<ll> lefts;vector<ll> rights;ll ans = -2e9;ll h, w;void dfs(){if (way.size() == 2){ll p = way[0];ll q = way[1];// debug(vector<ll>({p, q}));auto [p_min, p_max] = lim[p];auto [q_min, q_max] = lim[q];for (ll i = p_min; i < p_max; i++){for (ll j = q_min; j < q_max; j++){if (p == q && i == j){continue;}ll tmp = sum[p][i] + sum[q][j];ll a, b, c, d;a = lefts[p];b = rights[p];c = lefts[q];d = rights[q];// debug(vector<ll>({i, j}));// debug(vector<ll>({a, b, c, d}));// debug(tmp);ll disc = a * d - b * c;// debug(disc);if (disc){ll u = (i * d - j * b) / disc;ll v = (-i * c + j * a) / disc;// debug(vector<ll>({u, v}));if (0 <= u && u < h){if (0 <= v && v < w){tmp -= maze[u][v];}}}// debug(tmp);auto chmax = [](auto &a, auto b){ a = max(a, b); };chmax(ans,tmp);}}return;}rep(i, 4){way.push_back(i);dfs();way.pop_back();}}int main(){cin >> h >> w;lim[0] = {0, h};lim[1] = {0, w};lim[2] = {0, h + w - 1};lim[3] = {-w + 1, h};lefts = {1, 0, 1, 1};rights = {0, 1, 1, -1};maze.resize(h, vector<ll>(w));cin >> maze;// cout << maze << endl;rep(i, h){rep(j, w){sum[0][i] += maze[i][j];sum[1][j] += maze[i][j];sum[2][i + j] += maze[i][j];sum[3][i - j] += maze[i][j];}}// rep(i, 4)// {// cout << sum[i] << endl;// }dfs();cout << ans << endl;}