Page **1** of **2**

### 10520 - Determine it

Posted: **Thu Jul 03, 2003 4:33 pm**

by **Alexander Kozlov**

Dear friends!

I have just got AC for this problem.

I consider j >= 1. That is 1 <= i,j <= n and

.......................| max(aik + ank),...j > 1

aij = ........ + <...................................i >= j

.......................| 0, .......................j = 1

Posted: **Thu Jul 03, 2003 5:25 pm**

by **Larry**

Can you post some examples?

Posted: **Fri Jul 04, 2003 1:34 am**

by **Lars Hellsten**

Maybe he means that the j = 0 (j > 0) condition in the problem statement should actually be j = 1 (j > 1). You'll never actually consider j = 0 because k always starts at 1. If you implement this in the obvious way, your loop condition will probably do this check implicitly though.

Anyway, this problem is straightforward, aside from the not-quite-obvious-without-testing fact answers can be larger than 2^32.

Posted: **Fri Jul 04, 2003 9:28 am**

by **Larry**

I used long long and got WA, is this enough or do I need bigint?

### Some tests

Posted: **Fri Jul 04, 2003 9:42 am**

by **Alexander Kozlov**

Input:

5 10

4 1

6 13

10 36

11 243

14 67

15 198

16 325

17 423

19 499

Output:

1140

42

3770

313416

4728294

13721734

87589260

308839050

859374414

4578345958

Posted: **Fri Jul 04, 2003 7:12 pm**

by **Larry**

Thanks. Stupid mistake, I changed my stuff from int to long long and didn't remember to change one of the intermediate variables..

### Sorry

Posted: **Sun Aug 03, 2003 6:30 am**

by **shihabbd81**

the coditions should be j>1 and j=1 not j>0 and j=0

it was my mistake.

sorry.

Shihab Uddin

problemsetter of 10520

Posted: **Sat Jun 05, 2004 12:09 pm**

by **Examiner**

Then the formula implies a[n, 1] is always 0; this contradicts the input, unless the second number is also 0.

### 10520...check my I/O

Posted: **Thu Aug 03, 2006 5:21 pm**

by **asif_rahman0**

can someone check my following Input/output.

my code gives the following answer:

Code: Select all

```
Input:
1 2
1 1
1 9
1 15
15 1
9 1
2 1
10 10
13 6
15 105
15 350
15 450
19 450
17 319
17 400
11 411
17 411
19 19
Output:
2
1
9
15
442370
3842
4
87060
565260
46448850
154829500
199066500
4128768900
648086142
812647200
7997238
834994998
174325798
```

**Output is now corrected.**
rabbi

Posted: **Thu Aug 03, 2006 5:28 pm**

by **mf**

I get a different output only for 19 450 -- 4128768900.

Posted: **Thu Aug 03, 2006 5:54 pm**

by **asif_rahman0**

thnx mf.

Got accepted.

It should be 64 bit data type.

Posted: **Sat Aug 05, 2006 3:32 am**

by **Martin Macko**

asif_rahman0 wrote:thnx mf.

Got accepted.

It should be 64 bit data type.

Please, fix the output to the

**19 450** case in your very first post in this thread, so people won't get confused by the incorrect output.

Posted: **Sun Oct 21, 2007 6:29 am**

by **mhayter1**

Hi, I've past all test cases on the forum, and I use a 64 bit data type without success. Could anyone help?

Code: Select all

```
#include<iostream>
#include<algorithm>
using namespace std;
const unsigned long long SIZE=500;
unsigned long long memo[SIZE][SIZE];
bool found[SIZE][SIZE];
unsigned long long n;
inline void update(unsigned long long i,unsigned long long j,unsigned long long v)
{
memo[i][j]=v;
found[i][j]=true;
}
inline unsigned long long mx(unsigned long long &a,unsigned long long &b)
{
if(a>=b)return a;
else return b;
}
unsigned long long zzz;
unsigned long long a(unsigned long long i,unsigned long long j)
{
if(found[i][j]) return memo[i][j];
if(i>=j)
{
unsigned long long s1=0;
unsigned long long s2=0;
if(i<n)
{
for(unsigned long long k=i+1;k<=n;k++)
{
unsigned long long ak1=a(k,1);
update(k,1,ak1);
unsigned long long akj=a(k,j);
update(k,j,akj);
unsigned long long sum=ak1+akj;
s1=mx(s1,sum);
}
}
else if(i==n)
{
s1=0;
}
if(j>1)
{
for(unsigned long long k=1;k<j;k++)
{
unsigned long long aik=a(i,k);
update(i,k,aik);
unsigned long long ank=a(n,k);
update(n,k,ank);
unsigned long long sum=aik+ank;
s2=mx(s2,sum);
}
}
else if(j==1)
{
s2=0;
}
unsigned long long aij=s1+s2;
update(i,j,aij);
return memo[i][j];
}
else
{
unsigned long long s1=0;
for(unsigned long long k=i;k<j;k++)
{
unsigned long long aik=a(i,k);
update(i,k,aik);
unsigned long long akonej=a(k+1,j);
update(k+1,j,akonej);
unsigned long long sum=aik+akonej;
s1=mx(s1,sum);
}
update(i,j,s1);
return memo[i][j];
}
}
int main()
{
while(cin>>n>>memo[n][1])
{
memset(found,0,sizeof(found));
found[n][1]=true;
cout<<(unsigned long long)a(1,n)<<endl;
}
unsigned long long z;
cin>>z;
return 0;
}
```

### Re: 10520 - Determine It

Posted: **Thu Jun 26, 2008 1:21 pm**

by **smilitude**

i checked your program in my pc with all possible inputs. and after comparing with my ac program's output, my judge program printed

Code: Select all

```
Total Case 9481; passed 9481; failed 0
```

which astonished me! i am not sure why its not working in judge.

i used devcpp, and it works fine in my pc.

### Re: 10520 - Determine It

Posted: **Mon Jul 21, 2008 10:26 pm**

by **andmej**

I solved this using top-down dynamic programming (memoization). I was wondering, is it possible to solve this in a bottom-up approach? Thanks.