Page 9 of 16
108...With lots of WA~~!!!
Posted: Fri Mar 04, 2005 3:55 pm
by Wei
I've gotton some WA...
But I don't even know where the wrong is...
Could someone can help me???
Code: Select all
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,a[102][102],i,j,k,l,max;
scanf("%d",&n);
max=-999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=a[i-1][j]+a[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=a[i][j]+a[i][j-1];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=0;k<=i;k++)
for(l=0;l<=j;l++)
{
if(i!=k||j!=l)
if(max<a[i][j]-a[k][l])
max=a[i][j]-a[k][l];
}
printf("%d\n",max);
/*system("PAUSE");*/
return 0;
}
Posted: Sat Mar 05, 2005 12:35 pm
by emotional blind
Look at this input
SAMPLE INPUT
Code: Select all
3
-100 -100 -100
-100 0 -100
-100 -100 -100
your out put is
But out put should be
Posted: Sat Mar 12, 2005 4:19 pm
by 58050zz
ImLazy wrote:
1. If a sub-array has maximum sum, it must begins with a positive number. Because if it begins with a negative number, it will only make it smaller.
how to do if i have
-1 5 5
5 0 0
5 0 0
Posted: Sat Mar 12, 2005 6:29 pm
by 58050zz
cyfra wrote:
B[i,j]:=b[i-1,j]+b[i,j-1]-b[i-1,j-1]+a[i,j] ...
And the whole program complexity is O(n^4)..
Try to implement this (this is quite an easy algoritm so try it )
Good Luck
if u have free time
plz give some help
i think i use ur algo with correct way
but still get WA
can u give me some samples
Code: Select all
#include <iostream>
using namespace std;
int main()
{
int a[101][101];
int b[101][101]={0};
int i,j,k,n=0;
int max=-999;
int temp;
cin>>n;
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;
return 0;
}
108 Maximum Sum
Posted: Mon Mar 21, 2005 5:57 am
by 58050zz
http://acm.uva.es/p/v1/108.html
help WA
Code: Select all
#include <iostream>
using namespace std;
void output(int a[][101],int b[][101],int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%3d",a[i][j]);
}
printf("\n");
}
printf("=========\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%3d",b[i][j]);
}
printf("\n");
}
}
int main()
{
int a[101][101];
int b[101][101]={0};
int i,j,k,n=0;
int max=-999;
int temp;
cin>>n;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[i][j];
if(a[i][j]>max)
{//if max
max=a[i][j];
}
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
//make b table
//pic1
if(b[i][j]>max)
{//if max
max=b[i][j];
}
}
}
//output(a,b,n);
for(i=1;i<=n;i++)
{//implement b table
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(k<j)
{//pic 2
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)
{//pic 3
temp=b[i][j]-b[k][j]-b[i][k]+b[k][k];
if(temp>max) max=temp;
}
}
}
}
cout<<max<<endl;
return 0;
}
Posted: Mon Mar 21, 2005 6:01 am
by 58050zz
my algorithm
http://online-judge.uva.es/board/viewto ... hlight=108
cyfra wrote:Thanks for explanation...
but I will write you here a simplier (I hope
method....
Let us make a table B...
the B[i,j] = sum (from 1 to i and form 1 to j of A)
that means that B[1,1]=A[1,1] B[1,2]:=A[1,1]+A[1,2]; ... B[2,2]= A[1,1]+A[1,2]+A[2,1]+A[2,2]....
and if you have this table the sum of the rectangle for exmple form 2,2 to 4,5 is equal to :
B[4,5]-B[4,1]-B[1,5]+B[1,1] (if you don't believe you can check
So if you have table B you can solve this problem in O(n^4) -- check all the possibilities in O(1) time as I wrote before...
If you are clever you can count the B table in O(n^2) time...
because B[i,j]:=b[i-1,j]+b[i,j-1]-b[i-1,j-1]+a[i,j] ...
And the whole program complexity is O(n^4)..
Try to implement this (this is quite an easy algoritm so try it )
Good Luck
..
Posted: Mon Mar 21, 2005 6:24 am
by 58050zz
..
Posted: Mon Mar 21, 2005 8:57 pm
by Emilio
Your algorithm is O(n^3) not O(n^4) how cyfra wrote
Problem 108
Posted: Tue Mar 22, 2005 12:55 pm
by Sakib
Anyone please help me to show the way how i can implement the O^4 or O^3 algorithm here.
I used O^6 but got TLE.
Please Help!
Posted: Tue Mar 22, 2005 2:37 pm
by mohiul alam prince
Hi
this is the O^3 algorithm
*
- first find out the maximum value for row-1
- then add first row and second row and find out the maximum value.
- then add third row first row and second row and find out the maximum value
- then forth row and up to N and continue.
*
- then again first select second row and find out maximum value
- then add third row and find out the maximum value.
- and N continue.
thanks:)
MAP
108 Maximum sum - Time limit exeeded
Posted: Wed Mar 23, 2005 11:25 am
by nicu_ivan
Hye, I have a problem (time limit exedeed). I used a O^6 algoritm and I need help In makeing a faster algoritm.
Here is my code:
Code: Select all
var n,i,j,k,r,suma,yes,max:longint;
nr:array[1..110,1..110] of longint;
function sumarit(i1,j1,i2,j2:longint):longint;
var i,j,suma:longint;
begin
suma:=0;
for i:=i1 to i2 do
for j:=j1 to j2 do
suma:=suma+nr[i,j];
sumarit:=suma;
end;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
read(nr[i,j]);
suma:=0;
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
for r:=1 to n do
begin
yes:=sumarit(i,j,k,r);
if yes>suma then
suma:=yes;
end;
writeln(suma);
end.
Please give me a better idea. I really need one.
Posted: Wed Mar 23, 2005 11:49 am
by Observer
Hi,
For this task, an O(n^6) algorithm will never get accepted... Please
search the board for related topics. There are more than 30 of them.
Posted: Wed Mar 23, 2005 2:56 pm
by Sakib
Thanks for help.
I will try tour algorithm.
problem 108 WA(what's wrong with this code)
Posted: Sun May 08, 2005 4:58 pm
by dmn
I don't know why i got wa. I think it's good and it's work with my all inputs.
If anyone can tell me what's wrong with this code i will be appreciative.
Code: Select all
//o(n^4)
#include<iostream>
using namespace std;
int main(void)
{
const int m = 100;
int array[m][m];
int n;
while(cin>>n){
//read array
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>array[i][j];
//calculate maximum summ
int max=array[0][0];
for(int k=0;k<n;k++)
for(int i=0;i<n-k;i++){
bool in=false;
int Q,j;
for(j=0,Q=array[i][j];j<n;j++){
int q=0;
for(int l=0;l<=k;l++)
q+=array[i+l][j];
if(q<0){
if(in){
in=false;
if(Q>max) max=Q;
}
else if(q>max) max=q;
}
else{
if(!in){
in=true;
Q=q;
}
else Q+=q;
}
}
if(Q>max) max=Q;
}
cout<<max<<endl;
}
return 0;
}
Re: problem 108 WA(what's wrong with this code)
Posted: Mon May 09, 2005 6:33 pm
by dmn
Ok I know what's wrong and i solved it so don't bother it