Show all threads Hide all threads Show all messages Hide all messages 
Why WA 11?  Kirill~  1146. Maximum Sum  23 Oct 2021 19:53  1 

WA 4. Can anybody give some tests. You can see my code.  Minayev {SESC USU}  1146. Maximum Sum  25 Sep 2020 19:10  3 
oh i found my mistake Edited by author 03.11.2014 12:28 4 1 2 3 4 5 0 7 8 9 1 127 100 3 4 7 1 I have WA on tc 4 too and am unable to figure it out. Some help? 
No subject  D4nick  1146. Maximum Sum  6 Apr 2020 16:04  1 
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector <vector <int>> a(n, vector <int> (n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } int ans = a[0][0]; for (int leng = 1; leng <= n; leng++){ for (int up = 0; up <= nleng; up++){ vector <long long> sumv(n); for (int j = 0; j < n; j++) { for (int i = up; i < up + leng; i++) { sumv[j] += a[i][j]; } } int sum = 0; for (int r = 0; r < n; ++r) { sum += sumv[r]; ans = max(ans, sum); sum = max(sum, 0); } } } cout << ans; } 
I know there O(N^3) solution, but how to get 0.001s ??  xurshid_n  1146. Maximum Sum  7 Nov 2019 21:19  2 
There a[i][j] in [127..127] and n <= 100  May be there bitmask tricks, or other tricks???? There's one hard solution with quick matrix multiply 
Getting wrong answer for test case #3  Aakanksha Sharma  1146. Maximum Sum  3 Sep 2019 16:44  1 
My code is as following: #include<iostream> #include<vector> using namespace std; long getMaxSumRow(long rowArr[], int n) { long cs = 0; long ms = 0; bool positiveNumberPresent = false; for (int i = 0; i < n; i++) { if (!positiveNumberPresent && (rowArr[i] >= 0)) { positiveNumberPresent = true; } cs += rowArr[i]; if (cs < 0) { cs = 0; continue; } if (cs > ms) { ms = cs; } } if (positiveNumberPresent) { return ms; } ms = rowArr[0]; for (int i = 0; i < n; i++) { if (rowArr[i] > ms) { ms = rowArr[i]; } } return ms; } long maxSumRec(vector<vector<long> > &arr, int n) { if (n == 1) { return arr[0][0]; } /* Take an array for running rows sum */ long runningRowSum[n]; for (int r = 0; r < n; r++) { runningRowSum[r] = 0; } long maxSum = INT_MIN; /* Initialize variables for leftright and topbottom bounds */ int left, right, top = 0, bottom = n1; /* Iterate from all possible lefts to all possibe rights ahead of this left */ for (left = 0; left < n; left++) { for (right = 0; right < n; right++) { for (top = 0; top <= bottom; top++) { runningRowSum[top] += arr[top][right]; } /* For this leftright combination, calculate contigeous subarray with maximum sum in runningRowSum */ long currSum = getMaxSumRow(runningRowSum, n); if (currSum > maxSum) { maxSum = currSum; } } /* Reinitialize running row sum to 0 */ for (int r = 0; r < n; r++) { runningRowSum[r] = 0; } } return maxSum; } int main() { int n; cin >> n; vector<vector<long> > arr(n); for (int i = 0; i < n; i++) { arr[i] = vector<long>(n); for (int j = 0; j < n; j++) { cin >> arr[i][j]; } } cout << maxSumRec(arr, n); return 0; } But I am getting wrong answer for test case#3 . Any advice on what it might be failing at ? 
Is it possible to solve the problem with Python?  Edmonton  1146. Maximum Sum  20 Aug 2019 00:25  1 
I can't understand how to solve the problem with Python and meet time limitations. I implemented solution with creating 3D list of subsumes[column][row_start][row_offset] using accumulate from itertools and list comprehension. After that I used Kadane's algorithm. I expect that it works with O(N^3). But it isn't enough... Are there some tricks in the problem for Python? Except for stdin of course. 
Some Hint  Locomotive  1146. Maximum Sum  20 Nov 2018 21:48  6 
1use dynamic 2i got AC with 22lined program and 2array [1..100,1..100] (one integer and one longint)(pascal) 3answer of this sample is 1 1 2 3 3 2 1 1 2 3 4its best order is O(n^3). For other elp mail me Sincerely Aidin_n7@hotmail.com Thank you for test!! I got AC! 1use dynamic 2i got AC with 22lined program and 2array [1..100,1..100] (one integer and one longint)(pascal) 3answer of this sample is 1 1 2 3 3 2 1 1 2 3 4its best order is O(n^3). For other elp mail me Sincerely Aidin_n7@hotmail.com Thanks... :) I got AC too... i have O(n^3)solution. but wrong answer on test 7. Can you give me some test cases please? 
WA#2  Zhanibek  1146. Maximum Sum  26 Dec 2017 10:59  1 
WA#2 Zhanibek 26 Dec 2017 10:59 Please, give me some tests! 
Is O(n^3) solution  DP one?  SupremeEntropy  1146. Maximum Sum  25 Jul 2017 23:18  3 
Solution looks like bruteforce with a precalc, not a dynamic programming one. Or precalc counts as DP? Or DP is just a clever bruteforce? Edited by author 25.07.2017 20:10 Are you calculating something like "maximal sum subarray" ? That is where it is DP. If you are doing Kadane algorithm You are doing essentially that thing dp[i] = max(0, dp[i1] + matrix [i]) answer = max(dp[i]) 
This is WEIRD  iOli  1146. Maximum Sum  28 Jun 2017 13:20  3 
My solution passes first 4 test cases and shows memory limit exceeded error at 5th test case. I have made a global 4D array 100*100*100*100 which keeps the result of the sum of a rectangle whose top left corner is x1,y1 and bottom right corner is x2,y2, 4d array mat[x1][y1][x2][y2] stores the sum of the numbers corresponding to that rectangle. Now if this big array were a reason behind memory limit exceeded error than it shouldn't have passed even the first test cases because i made global 4d array of maximum size by default. So what can be the reason? #include <iostream> using namespace std; const int M = 107; int mat[M][M][M][M]; int main() { int n; cin >> n; int arr[n][n]; int ans = 1e9; for (int i=0; i<n; i++) for (int j=0; j<n; j++) { cin >> arr[i][j]; mat[i][j][i][j] = arr[i][j]; if (arr[i][j] > ans) ans = arr[i][j]; } for (int size = 2; size<=n*n; size++) { for (int p=1; p<=size and p<=n; p++) { int q = size/p; if (p*q != size) continue; for (int i=0; i<np+1; i++) { for (int j=0; j<nq+1; j++) { int x1 = i, y1 = j; int x2 = i+p1, y2 = j+q1; if (x2x1 > y2y1) { mat[x1][y1][x2][y2] = mat[x1][y1][x21][y2] + mat[x2][y1][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } else { mat[x1][y1][x2][y2] = mat[x1][y1][x2][y21] + mat[x1][y2][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } } } } } cout << ans << endl; } Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:07 Actually, if you don't access your global allocated memory, that memory don't counts. I have noticed that when watching how my solutions are testing. When there is a global array of big size first few cases are low memory. And last test cases are high memory usage. You can find any simple task were you are to output some string. Allocate a HUGE buffer for that string. Then submit your solution. Then allocate a buffer just enough to hold your string and submit again. And you will see that memory usage is the SAME. 
if WA#8  liushujia  1146. Maximum Sum  15 Apr 2016 13:46  8 
if WA#8 liushujia 24 Aug 2011 18:59 try this: sample input: 2 1 2 3 4 sample output: 1 
WOW! AC 0.296, 237 KB O(n^4) works! Can U describe me O(n^3) solution?  Alexey  1146. Maximum Sum  25 Mar 2016 19:13  6 
I cann't believe it! Dynamika O(n^4). Can you give me some hints about algo O(n^3)? Is it Dynamika too? Thanks a lot! Edited by author 04.06.2006 14:57 So, your solution O(N^4) was accepted? I know O(N^4), and O(N^3) (but it requires O(N^3) memory). I can tell you the last. So, what's the O(n^3) solution ? Hint: Solve problem 1296 first. And use it's solution. Hint: Solve problem 1296 first. And use it's solution. Yeah... That's right. Thanks a lot for the hint.... It worked. 
WA 5  Artem  1146. Maximum Sum  11 Nov 2015 06:33  3 
WA 5 Artem 9 Sep 2012 12:59 My program gets WA #5. Did anybody have the same problem? Program works correctly with all inputs I have found. Edited by author 09.09.2012 13:01 
o(n^4) ACCEPTED!!! 0.078 s  Temirbay Miras  1146. Maximum Sum  6 Nov 2015 02:11  2 
Also accepted O(n^4) in Go 0.312 As task marked easy, it was lazy for me to implement O(n^3) 
One more test (about WA4)  FatalityNT  1146. Maximum Sum  1 Nov 2015 13:31  2 
Firstly my solution got TLE#4. Next, I make mew solution with new idea, and got WA#4. Also, my 2nd solution makes mistake in this test: 4 0 2 1 0 9 2 9 2 4 1 1 1 1 8 10 2 answer is 18. It can help someone. P.S. forry for bad English. 
Hi, everybody! Can you explain me, what is the #9 test?  AndrKonin  1146. Maximum Sum  12 Oct 2015 21:35  3 
I haven't idea how to approach this test? my code is simple O(n^4),but #9 test doesn' work: for (i=1;i<=n;i++) { for (j=1;j<=n;j++)
s[i][j]=s[i1][j]+s[i][j1]+a[i][j]s[i1][j1];
} for (i=1;i<=n;i++) for (j=1;j<=n;j++) { for (k=i;k<=n;k++) { for (m=j;m<=n;m++) { sum=s[k][m]s[i1][m]s[k][j1]+s[i1][j1];
if (sum>max1) max1=sum;
} } } I had the same problem. Firstly I used array of short and there was overflow in sum (max possible sum is 127 * 100 * 100 = 1270000 > 32767). Then I changed type to int and got AC :) 
there is a solution with almost O(n)  maxi  1146. Maximum Sum  29 Apr 2015 20:50  2 
#include <iostream> using namespace std; int n,A[1002],i,maxi,S[1002],st,dr,rez; int main() { cin>>n; for(i=1;i<=n;i++) cin>>A[i]; S[1]=A[1]; for(i=1;i<=n;i++) if(S[i1]<=0) S[i]=A[i]; else S[i]=A[i]+S[i1]; rez=1000000; for(i=1;i<=n;i++) if(S[i]>rez) rez=S[i]; cout<<rez; return 0; } it's just a joke, isn't it? 
Does anybody have O(n^2) algorithm ?  hkss  1146. Maximum Sum  20 Mar 2015 15:12  2 
please help me if you have O(n^2) algorithm for this problem . thanks From my knowledge i know there is possible only O(n^3) 
I've AC in O^4,but I wonder if there is a O^3 way  bbs.hasea.com  1146. Maximum Sum  19 May 2013 18:58  5 
code deleted Edited by author 13.09.2007 17:11 Your Solution C++: time = 0.187 Solutin in Pascal (other algorithm): time = 0.031 Pleace, delete your solution code :) There is an O(n^3) way(my solution is that). First you must save the sum of the elements form the first to each of the others in every row. Then for each column I and each column J (J>=I) you sum all the rows (using the first step). On each step you check if the sum now is better than the max.If the sum gets below zero you make it zero and continue. Kiril Kafadarov 1146 C++ Accepted 0.015 197 KB 
WA3. O(N^2) solution  Andrew Sboev  1146. Maximum Sum  10 Mar 2013 18:05  3 
Gimme some tests, please :) All tests that I found my program passed right, I can't understand my mistake. Now I have WA4 :) Edited by author 08.07.2012 10:07 can anybody explain me an idea of N^2? I think there is no O(N^2) solution, but who knows? Maybe, I'm not right. Now my AC solution is nearly O(N^3) (something like N^3N^4 operation)  it's enough. 