Untitled
unknown
plain_text
a year ago
1.2 kB
7
Indexable
// y.ha
#include <bits/stdc++.h>
#define cook '\n'
#define maxn
#define Task "bai1"
using namespace std;
vector<vector<int>> v,ps ;
int m,n ;
void inp() {
cin >> m >> n;
v.resize(m+1,vector<int>(n+1)) ;
for ( int i = 1; i <= m; i++ )
for ( int j = 1; j <= n; j++ )
cin >> v[i][j] ;
}
void pre_sum() {
ps.resize(m+1,vector<int>(n+1)) ;
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= m; j++ )
ps[j][i] = ps[j-1][i] + v[j][i] ;
}
int solve(int top,int bot) {
int sum = 0, res = -1e9;
for ( int i = 1; i <= n; i++ ) {
sum += ps[bot][i] - ps[top-1][i] ;
res = max(sum,res) ;
if ( sum < 0 ) sum = 0;
}
return res ;
}
int res() {
int result = -1e9 ;
for ( int top = 1; top <= m; top++ )
for ( int bot = top; bot <= m; bot++ )
result = max(result,solve(top,bot)) ;
return result ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(nullptr) ;
if(fopen(Task".inp","r")) {
freopen(Task".inp","r",stdin) ;
freopen(Task".out","w",stdout) ;
}
inp() ;
pre_sum() ;
cout << res() ;
}
Editor is loading...
Leave a Comment