Submission #617079

---

Source Code Expand

#ifndef KOMAKI_LOCAL
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top();   }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }

#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...)                                                      \
  {                                                                     \
    DBG_LINE();                                                         \
    DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
    DBG_OUT << std::endl;                                               \
  }





i64 solve(vector<vector<i64>> v)
{
  i64 n = sz(v);
  i64 m = sz(v[0]);

  vector<vector<i64>> l_sum = v;
  rep(i, n)rep(j, m)if(j) l_sum[i][j] += l_sum[i][j - 1];

  vector<vector<i64>> bests(m, vector<i64>(m + 1));
  rep(_r, m)rep(l, _r + 1){
      i64 r = _r + 1;
      vector<i64> a;
      rep(i, n){
        i64 total = 0;
        if(0 < l) total -= l_sum[i][l - 1];
        total += l_sum[i][_r];
        a.push_back(total);
      }
      i64 best_ending_here = a[0];
      i64 best_so_far = a[0];
      for(i64 i = 1; i < n; ++i){
        best_ending_here = max(a[i], best_ending_here + a[i]);
        best_so_far = max(best_so_far, best_ending_here);
      }
      //DEBUG(l, r, best_so_far);
      bests[l][r] = best_so_far;
    }

  i64 best = -bit(50);
  rep(delim, m)if(delim){
      i64 best_l = -bit(50);
      i64 best_r = -bit(50);
      for(i64 l = 0; l < delim; ++l){
        for(i64 _r = l; _r < delim; ++_r){
          best_l = max(best_l, bests[l][_r + 1]);
        }
      }
      for(i64 l = delim; l < m; ++l){
        for(i64 _r = l; _r < m; ++_r){
          best_r = max(best_r, bests[l][_r + 1]);
        }
      }
      best = max(best, best_l + best_r);
    }
  return best;
}


int main()
{
  i64 n, m;
  bool debug = !true;
  if(debug){
    n = 300;
    m = 300;
  }else{
    cin >> n >> m;
  }
  vector<vector<i64>> rec0(n, vector<i64>(m));
  vector<vector<i64>> rec1(m, vector<i64>(n));
  rep(i, n)rep(j, m){
      if(debug){
        rec0[i][j] = 100;
      }else{
        cin >> rec0[i][j];
      }
      rec1[j][i] = rec0[i][j];
    }
  cout << max(solve(rec0), solve(rec1)) << endl;
}

Submission Info

Judge Result