ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1220. Stacks

why memory limit?
Posted by Илья Гофман (Ilya Gofman) 29 Mar 2004 17:21
if i declare

type StackR=array[1..100000] of ^longint;
type Stack=^StackR;
var m:array[1..1000] of Stack;

does this mean that my program has used 100000x1000x4 = 4x10^9bytes? together with the fact that my variables are dynamic and I call the new() procedure not more than for 100000 longints?
Re: why memory limit?
Posted by Vladimir Yakovlev (USU) 29 Mar 2004 19:58
> not more than for 100000 longints?

plus not more than 100000 pointers (4 byte)

total: 800K of data => MLE
Re: why memory limit?
Posted by Илья Гофман (Ilya Gofman) 30 Mar 2004 19:57
thx, but then how do i make it? the actual part of the problem is nothing hard...
Re: why memory limit?
Posted by buggzy 30 Mar 2004 22:55
Use another data presentation and O(n*n) algorithm instead of O(n).
Re: why memory limit?
Posted by Vladimir Yakovlev (USU) 31 Mar 2004 00:11
The actual part of this problem is to do it in 750K