Untitled

 avatar
unknown
plain_text
6 months ago
1.2 kB
2
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