ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1146. Maximum Sum

Hi, everybody! Can you explain me, what is the #9 test?
Posted by AndrKonin 15 Sep 2013 06:28
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[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];

}
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[i-1][m]-s[k][j-1]+s[i-1][j-1];

if (sum>max1) max1=sum;

}
}
}
Re: Hi, everybody! Can you explain me, what is the #9 test?
Posted by mihai.alpha 6 Oct 2015 22:56
Same thing here!
Re: Hi, everybody! Can you explain me, what is the #9 test?
Posted by Shirokov Alexander 12 Oct 2015 21:35
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 :)