Page 13 of 16
108 maximum sum
Posted: Wed Dec 20, 2006 12:51 pm
by rezaee
oh.ok.
but i get WA.
#include <iostream.h>
int n;
int b[101][101];
int main()
{
int a[101][101];
int i,j,k;
int max;
int s;
while(cin>>n)
{max=-127;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[j];
if(a[j]>max)
{
max=a[j];
}
b[j]=b[i-1][j]+b[j-1]-b[i-1][j-1]+a[j];
if(b[j]>max)
{
max=b[j];
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(k<j)
{
s=b[j]-b[k];
if(s>max) max=s;
}
if(k<i)
{
s=b[i][j]-b[k][j];
if(s>max) max=s;
}
if(k<i && k<j)
{
s=b[i][j]-b[k][j]-b[i][k]+b[k][k];
if(s>max) max=s;
}
}
}
}
cout<<max<<endl;}
return 0;
}
Posted: Wed Dec 20, 2006 1:34 pm
by mogers
You should search before posting a new topic about one problem... there are a lot of threads about this problem...
instead of posting your code, first try to discuss your algorithm. Then, if you want to post the code, use de 'code' tag.
good luck
Posted: Wed Dec 20, 2006 5:02 pm
by huan086
b
[j]=b[i-1][j]+b[j-1]-b[i-1][j-1]+a[j];
You accessed b[0] without initialising the array... 
I believe you need to do so in c++. (not needed in VB though)
Search through the forum and see how others had done it. Your code is longer than the typical ones.
And debug before posting 
108 maximum sum
Posted: Wed Dec 20, 2006 5:22 pm
by rezaee
ok.
but my code does work correctly.
in my compiler.
i dont know what to do.
108 maximum sum
Posted: Wed Dec 20, 2006 9:14 pm
by rezaee
help me.
108 maximum sum
Posted: Wed Dec 20, 2006 9:15 pm
by rezaee
i get a WA.
please help me.
Code: Select all
#include <iostream.h>
int n;
int b[101][101];
void sefr(void)
{for(int i=0;i<=n;i++)
{b[0][i]=0;b[i][0]=0;}
}
void main()
{
int a[101][101];
int i,j,k;
int max;
int temp;
while(cin>>n)
{if(n==0)break;
max=-127;
sefr();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[i][j];
if(a[i][j]>max)
{
max=a[i][j];
}
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
if(b[i][j]>max)
{
max=b[i][j];
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(k<j)
{
temp=b[i][j]-b[i][k];
if(temp>max) max=temp;
}
if(k<i)
{
temp=b[i][j]-b[k][j];
if(temp>max) max=temp;
}
if(k<i && k<j)
{
temp=b[i][j]-b[k][j]-b[i][k]+b[k][k];
if(temp>max) max=temp;
}
}
}
}
cout<<max<<endl;}}
please give me some test case.
Posted: Wed Dec 20, 2006 10:06 pm
by Jan
Check the case
Input:
Code: Select all
20
-86 -20 87 108 -83 42 -124 -94 60 112 -32
-32 -51 125 -111 109 63 85 110 -46 -121
-58 -50 26 -90 15 -46 -26 -44 -122 -35
-76 109 -64 -43 -105 40 -93 78 77 16
-31 85 116 -49 -53 -31 -66 76 111 -80
-23 -105 -10 20 -18 -74 -76 117 -114 -51
103 -122 -70 -94 -111 -12 -110 12 81 34
-37 -47 -28 18 -77 89 119 41 106 122
1 -13 -63 14 -17 -6 109 34 -84 -13
-73 19 -24 55 -9 -74 -85 107 94 116
-122 -78 -49 -118 113 80 -116 -74 74 49
58 22 75 23 92 -125 -109 125 65 -111
-97 109 -106 43 -95 68 -108 79 -60 -62
3 -16 -78 69 -12 125 -26 30 -10 30
-80 86 56 28 112 -48 -59 124 101 -80
84 94 -102 -34 -29 8 79 20 -2 -57
112 -43 10 1 -19 -72 89 -95 -2 -36
109 67 -72 -121 -76 -64 122 -94 -123 -6
17 -74 87 26 16 -112 91 -105 85 31
-24 41 -84 85 -1 -97 115 -9 -48 -98
94 -62 -16 73 22 72 64 -24 86 -23
-84 107 97 72 -65 8 -42 -94 -64 51
-70 117 -59 -74 83 71 116 53 34 -119
109 82 16 87 0 -55 35 51 -75 46
82 -42 -50 -74 -56 53 66 -96 -91 10
-43 -80 38 56 79 -30 -86 -122 1 -93
125 2 14 79 -4 -5 -91 -51 -38 115
44 -30 37 103 -125 -77 88 -34 -33 -116
26 14 -28 83 -24 30 3 85 -42 -69
-66 -70 -85 15 -50 -38 -13 94 -23 -41
92 -54 5 -122 -27 -8 102 -81 -50 -72
83 -84 56 -53 56 87 114 -15 -93 -18
-30 104 72 66 118 110 -111 109 -87 -119
90 88 107 -118 99 79 -111 49 -104 106
3 -52 36 20 -29 -80 -92 106 89 -111
51 59 60 99 -63 119 -50 117 -6 53
-77 81 -116 -68 112 -100 47 41 7 17
58 28 122 54 26 12 100 1 121 45
88 -19 124 -125 -72 85 -48 7 -58 -118
-8 20 -113 -24 -107 -35 120 -4 -110
Hope it helps.
108 Why Compile Error at Submit??
Posted: Mon Feb 05, 2007 8:43 am
by FilePointer
The Code is...
Code: Select all
#include <iostream>
using namespace std;
short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };
int main( int argc, char **argv )
{
int MaxSum = -999999;
int size;
cin >> size;
for( int i = 1; i <= size; i++ ) {
for( int j = 1; j <= size; j++ ) {
cin >> Matrix[ i ][ j ][ i ][ j ];
}
}
for( int StartI = 1; StartI <= size; StartI++ ) {
for( int StartJ = 1; StartJ <= size; StartJ++ ) {
for( int EndI = StartI; EndI <= size; EndI++ ) {
for( int EndJ = StartJ; EndJ <= size; EndJ++ ) {
short RectangleSum, LineSum;
if( StartJ == EndJ )
RectangleSum = 0;
else
RectangleSum = Matrix[ StartI ][ StartJ ][ EndI ][ EndJ - 1 ];
if( StartI == EndI )
LineSum = 0;
else
LineSum = Matrix[ StartI ][ EndJ ][ EndI - 1 ][ EndJ ];
short NewLineSum = LineSum + Matrix[ EndI ][ EndJ ][ EndI ][ EndJ ];
Matrix[ StartI ][ EndJ ][ EndI ][ EndJ ] = NewLineSum;
short NewRectangleSum = RectangleSum + NewLineSum;
Matrix[ StartI ][ StartJ ][ EndI ][ EndJ ] = NewRectangleSum;
if( MaxSum < NewRectangleSum )
MaxSum = NewRectangleSum;
}
}
}
}
cout << MaxSum;
return 0;
}
There isn't Error in VS.NET 2003 & Cygwin( gcc 3.4.4 ) & Dev-C++ lastest version
What is reason for Compile Error?
Posted: Tue Feb 06, 2007 1:10 pm
by shamim
change this line
Code: Select all
short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };
to
Code: Select all
short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] ;
But it will get MLE now.
presentation error in 108
Posted: Fri Mar 23, 2007 4:56 am
by Fauhat(AUST)
Dear judges,
I am getting presentation error in 108(maximum sum). But I cannot understand why it is happening. I am printing only the result without giving any space and new line as the sample output indicates.
Will you kindly help me replying this mail saying the correct form of printing the result?
Regards,
Fauhat Ali Khan Panni(AUST)
108 - WA ??? Need help !!!
Posted: Fri Mar 23, 2007 9:14 pm
by namanh
Here's my code in Java. I have tried all test that i found on this forum, and the result is correct in all case. But i still got WA.
Anybody know why ?
Code: Select all
import java.util.*;
import java.io.*;
class Main {
static void main(String[] args) {
String input = ReadLn(255);
StringTokenizer idata = new StringTokenizer (input);
int n = Integer.parseInt(idata.nextToken());
int[][] a = new int[n][n];
int i=0,j=0;
while(i < n && (input = ReadLn(255)) != null ) {
idata = new StringTokenizer(input);
while(idata.hasMoreTokens()) {
a[i][j] = Integer.parseInt(idata.nextToken());
j++;
if(j == n) {
j=0;
i++;
}
}
}
System.out.println(maxTwoDimension(a));
}
static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}
static int maxTwoDimension(int[][] a) {
int n = a.length;
int m = a[0].length;
int[][] best = new int[m][m];
int[][][] b = new int[n][m][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
for(int k = j; k < m; k++){
if(j==0 && k ==0) b[i][j][k] = a[i][0];
if(j==0 && k > 0) b[i][j][k] = b[i][j][k-1] + a[i][k];
if(j > 0 )
b[i][j][k] = b[i][0][k] - b[i][0][j-1];
}
}
}
int[] temp = new int[n];
for(int j = 0; j < m; j++) {
for(int k = j; k <m; k++) {
for(int i = 0; i < n; i++)
temp[i] = b[i][j][k];
best[j][k] = maxOneDimension(temp);
}
}
int max = best[0][0];
for(int j = 0; j < m; j++) {
for(int k = j; k < m; k++) {
if (best[j][k] > max) max = best[j][k];
}
}
return max;
}
static int maxOneDimension(int[] temp) {
int n = temp.length;
int[] best = new int[n];
for(int i = 0; i < n; i++)
best[i] = temp[i];
int max = best[n-1];
for(int i = n-2; i >=0; i--) {
if(best[i+1] >0) best[i] +=best[i+1];
if(best[i] > max) max = best[i];
}
return max;
}
}
Posted: Sat Mar 24, 2007 10:57 am
by shamim
without giving any space and new line as the sample output indicates
not including space is ok, but why don't you print new lines. In every problem, there is at least one new line after every case of output.
Prob 108 :Time Limit Exceeded :Please Help
Posted: Mon Jun 11, 2007 8:14 am
by duleb
the source code is
#include<iostream>
using namespace std;
main()
{
int f=0,s=0;
short int a[90][90],i,j=0,k=0,m=0,x,y,n=0;
cin>>n;
for(x=0;x<n;x++)
for(y=0;y<n;y++)
cin>>a[x][y];
x=0;
while( k<=n)
{
for(i=m;i<n;i++)
for(j=0;j<=x;j++)
{
f+=a[j];
if(f>s)
s=f;
}
if(i==n)
{
x++; f=0;
}
if(x==n)
{
m++; x=0;
}
if(m==n)
{
k++; x=m=0;
}
}
cout<<s;
}
On My PC It Takes almost no time to execute (On Fedora 6) ;while submitting ,it is showing that program is exceeding 10 second.
So Please HELP me out.
Posted: Mon Jun 11, 2007 1:16 pm
by Jan
Search the board first. Dont open a new thread if there is one already.
Posted: Wed Jul 04, 2007 11:20 pm
by renato_ferreira
Hello, I need to optimize this code (TLE), but I have no idea how to do this, can you help me?
Code: Select all
#include <stdio.h>
int max = -9999, matriz[101][101], lado;
void busca(int altura, int largura);
int main()
{
int valor, i, j;
scanf("%d", &lado);
for (i = 0; i < lado; i++)
{
for (j = 0; j < lado ; j++)
{
scanf("%d", &valor);
matriz[i][j] = valor;
}
}
for (i = 0; i <= lado; i++)
{
for (j = 0; j <= lado; j++)
{
busca(i, j);
}
}
printf("%d", max);
return 0;
}
void busca(int altura, int largura)
{
int i, j, k, soma, g;
for (i = 0; i < (lado - altura); i++)
{
for (j = 0; j < (lado - largura); j++)
{
soma = 0;
for (g = i; g < (lado - altura); g++)
{
for (k = j; k < (lado - largura); k++)
{
soma += matriz[g][k];
}
}
if (soma > max)
{
max = soma;
}
}
}
}
Thank you.