108 - Maximum Sum

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

108 maximum sum

Post by rezaee » Wed Dec 20, 2006 12:51 pm

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;
}

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Wed Dec 20, 2006 1:34 pm

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
Miguel Oliveira

huan086
New poster
Posts: 5
Joined: Tue Dec 19, 2006 5:01 pm

Post by huan086 » Wed Dec 20, 2006 5:02 pm

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 8)

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

108 maximum sum

Post by rezaee » Wed Dec 20, 2006 5:22 pm

ok.

but my code does work correctly.

in my compiler.

:(

i dont know what to do.

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

108 maximum sum

Post by rezaee » Wed Dec 20, 2006 9:14 pm

help me.
Last edited by rezaee on Wed Dec 20, 2006 9:16 pm, edited 1 time in total.

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

108 maximum sum

Post by rezaee » Wed Dec 20, 2006 9:15 pm

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. :cry:

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Dec 20, 2006 10:06 pm

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 
Output:

Code: Select all

1864
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

FilePointer
New poster
Posts: 1
Joined: Mon Feb 05, 2007 8:41 am

108 Why Compile Error at Submit??

Post by FilePointer » Mon Feb 05, 2007 8:43 am

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?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Feb 06, 2007 1:10 pm

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.

Fauhat(AUST)
New poster
Posts: 3
Joined: Thu Mar 22, 2007 6:21 am
Location: Bangladesh

presentation error in 108

Post by Fauhat(AUST) » Fri Mar 23, 2007 4:56 am

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)
*fauhat A.K. panni*

namanh
New poster
Posts: 1
Joined: Fri Mar 23, 2007 9:05 pm

108 - WA ??? Need help !!!

Post by namanh » Fri Mar 23, 2007 9:14 pm

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;
  }
}

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Mar 24, 2007 10:57 am

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.

duleb
New poster
Posts: 4
Joined: Mon Jun 11, 2007 8:06 am

Prob 108 :Time Limit Exceeded :Please Help

Post by duleb » Mon Jun 11, 2007 8:14 am

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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jun 11, 2007 1:16 pm

Search the board first. Dont open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Wed Jul 04, 2007 11:20 pm

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.

Post Reply

Return to “Volume 1 (100-199)”