Untitled
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