Facebook
From Flying Macaque, 4 Weeks ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 53
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef double db;
  7. typedef string str;
  8.  
  9. typedef pair<int,int> pi;
  10. typedef pair<ll,ll> pl;
  11. typedef pair<db,db> pd;
  12.  
  13. typedef vector<int> vi;
  14. typedef vector<ll> vl;
  15. typedef vector<db> vd;
  16. typedef vector<str> vs;
  17. typedef vector<pi> vpi;
  18. typedef vector<pl> vpl;
  19. typedef vector<pd> vpd;
  20.  
  21. #define mp make_pair
  22. #define f first
  23. #define s second
  24. #define sz(x) (int)(x).size()
  25. #define all(x) begin(x), end(x)
  26. #define rall(x) (x).rbegin(), (x).rend()
  27. #define rsz resize
  28. #define ins insert
  29. #define ft front()
  30. #define bk back()
  31. #define pf push_front
  32. #define pb push_back
  33. #define eb emplace_back
  34. #define lb lower_bound
  35. #define ub upper_bound
  36.  
  37. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  38. #define F0R(i,a) FOR(i,0,a)
  39. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  40. #define R0F(i,a) ROF(i,0,a)
  41. #define trav(a,x) for (auto& a: x)
  42.  
  43. const int MOD = 1e9+7; // 998244353;
  44. const int MX = 2e5+5;
  45. const ll INF = 1e18;
  46. const ld PI = acos((ld)-1);
  47. const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
  48. //mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  49.  
  50. template<class T> bool ckmin(T& a, const T& b) {
  51.     return b < a ? a = b, 1 : 0; }
  52. template<class T> bool ckmax(T& a, const T& b) {
  53.     return a < b ? a = b, 1 : 0; }
  54. constexpr int pct(int x) { return __builtin_popcount(x); }
  55. constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
  56. ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
  57. ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
  58. ll half(ll x) { return fdiv(x,2); }
  59.  
  60. template<class T, class U> T fstTrue(T lo, T hi, U f) {
  61.     hi ++; assert(lo <= hi); // assuming f is increasing
  62.     while (lo < hi) { // find first index such that f is true
  63.         T mid = half(lo+hi);
  64.         f(mid) ? hi = mid : lo = mid+1;
  65.     }
  66.     return lo;
  67. }
  68. template<class T, class U> T lstTrue(T lo, T hi, U f) {
  69.     lo --; assert(lo <= hi); // assuming f is decreasing
  70.     while (lo < hi) { // find first index such that f is true
  71.         T mid = half(lo+hi+1);
  72.         f(mid) ? lo = mid : hi = mid-1;
  73.     }
  74.     return lo;
  75. }
  76. template<class T> void remDup(vector<T>& v) {
  77.     sort(all(v)); v.erase(unique(all(v)),end(v)); }
  78.  
  79. // INPUT
  80. template<class A> void re(complex<A>& c);
  81. template<class A, class B> void re(pair<A,B>& p);
  82. template<class A> void re(vector<A>& v);
  83. template<class A, size_t SZ> void re(array<A,SZ>& a);
  84.  
  85. template<class T> void re(T& x) { cin >> x; }
  86. void re(db& d) { str t; re(t); d = stod(t); }
  87. void re(ld& d) { str t; re(t); d = stold(t); }
  88. template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
  89.  
  90. template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
  91. template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
  92. template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
  93. template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
  94.  
  95. // TO_STRING
  96. #define ts to_string
  97. str ts(char c) { return str(1,c); }
  98. str ts(const char* s) { return (str)s; }
  99. str ts(str s) { return s; }
  100. str ts(bool b) {
  101. #ifdef LOCAL
  102.     return b ? "true" : "false";
  103. #else
  104.     return ts((int)b);
  105. #endif
  106. }
  107. template<class A> str ts(complex<A> c) {
  108.     stringstream ss; ss << c; return ss.str(); }
  109. str ts(vector<bool> v) {
  110.     str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
  111.     res += "}"; return res; }
  112. template<size_t SZ> str ts(bitset<SZ> b) {
  113.     str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  114.     return res; }
  115. template<class A, class B> str ts(pair<A,B> p);
  116. template<class T> str ts(T v) { // containers with begin(), end()
  117. #ifdef LOCAL
  118.     bool fst = 1; str res = "{";
  119.                 for (const auto& x: v) {
  120.                         if (!fst) res += ", ";
  121.                         fst = 0; res += ts(x);
  122.                 }
  123.                 res += "}"; return res;
  124. #else
  125.     bool fst = 1; str res = "";
  126.     for (const auto& x: v) {
  127.         if (!fst) res += " ";
  128.         fst = 0; res += ts(x);
  129.     }
  130.     return res;
  131.  
  132. #endif
  133. }
  134. template<class A, class B> str ts(pair<A,B> p) {
  135. #ifdef LOCAL
  136.     return "("+ts(p.f)+", "+ts(p.s)+")";
  137. #else
  138.     return ts(p.f)+" "+ts(p.s);
  139. #endif
  140. }
  141.  
  142. // OUTPUT
  143. template<class A> void pr(A x) { cout << ts(x); }
  144. template<class H, class... T> void pr(const H& h, const T&... t) {
  145.     pr(h); pr(t...); }
  146. void ps() { pr("\n"); } // print w/ spaces
  147. template<class H, class... T> void ps(const H& h, const T&... t) {
  148.     pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
  149.  
  150. // DEBUG
  151. void DBG() { cerr << "]" << endl; }
  152. template<class H, class... T> void DBG(H h, T... t) {
  153.     cerr << ts(h); if (sizeof...(t)) cerr << ", ";
  154.     DBG(t...); }
  155.  
  156. // #define LOCAL
  157.  
  158. #ifdef LOCAL // compile with -DLOCAL
  159. #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  160. #else
  161. #define dbg(...) 0
  162. #define assert(...) 0
  163. #endif
  164.  
  165. // FILE I/O
  166. void setIn(str s) { freopen(s.c_str(),"r",stdin); }
  167. void setOut(str s) { freopen(s.c_str(),"w",stdout); }
  168. void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
  169. void setIO(str s = "") {
  170.     unsyncIO();
  171.     // cin.exceptions(cin.failbit);
  172.     // throws exception when do smth illegal
  173.     // ex. try to read letter into int
  174.     if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  175. }
  176.  
  177. int N;
  178. const int maxv = 102;
  179. int pre[maxv][maxv];
  180. int val[maxv][maxv];
  181.  
  182. int main() {
  183.  
  184.     cin >> N;
  185.  
  186.     for (int i = 1; i <= N; i++) {
  187.         for (int j = 1; j <= N; j++) {
  188.             cin >> val[i][j];
  189.             pre[i][j] = val[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
  190.         }
  191.     }
  192.  
  193.     int ans = INT_MIN;
  194.     for (int i1 = 1; i1 <= N; i1++) {
  195.         for (int j1 = 1; j1 <= N; j1++) {
  196.             for (int i2 = i1; i2 <= N; i2++) {
  197.                 for (int j2 = j1; j2 <= N; j2++) {
  198.                     ans = max(ans, pre[i2][j2] - pre[i1 - 1][j2] - pre[i2][j1 - 1] + pre[i1 - 1][j1 - 1]);
  199.                 }
  200.             }
  201.         }
  202.     }
  203.  
  204.     cout << ans;
  205. }