結果
問題 | No.2509 Beam Shateki |
ユーザー |
![]() |
提出日時 | 2023-10-20 22:10:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,919 bytes |
コンパイル時間 | 1,603 ms |
コンパイル使用メモリ | 129,340 KB |
最終ジャッジ日時 | 2025-02-17 09:37:02 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 (int i = 0; i < n; i++) #define rep1(i, n) for (int i = 1; i < n + 1; i++) #define rev(i, n) for (int 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 (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << endl; } return os; } template <typename T> ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) { int n = v.size(); int m = v[0].size(); int 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 (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template <typename T> ostream &operator<<(ostream &os, multiset<T> st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)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<int>> maze; vector<int> way; vector<map<int, int>> sum(4); map<int, pair<int, int>> lim; vector<int> lefts; vector<int> rights; int ans = -2e9; int h, w; void dfs() { if (way.size() == 2) { int p = way[0]; int q = way[1]; // debug(vector<int>({p, q})); auto [p_min, p_max] = lim[p]; auto [q_min, q_max] = lim[q]; for (int i = p_min; i < p_max; i++) { for (int j = q_min; j < q_max; j++) { if (p == q && i == j) { continue; } int tmp = sum[p][i] + sum[q][j]; int a, b, c, d; a = lefts[p]; b = rights[p]; c = lefts[q]; d = rights[q]; // debug(vector<int>({i, j})); // debug(vector<int>({a, b, c, d})); // debug(tmp); int disc = a * d - b * c; // debug(disc); if (disc) { int u = (i * d - j * b) / disc; int v = (-i * c + j * a) / disc; // debug(vector<int>({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<int>(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; }