OJ Board

Hello,
I've been trying for some time to solve this problem, and i have no idea, why i get WA all the time. Is there any trick in this task? I solve it with DP, for each k and l, i find the maximum number of ridings, if you can use k avenues to divide, and the last to the north would be l avenue. Do I have to choose avenues 1 and 100 too? (i tried both versions).
Best regards,
Furippo

Hi!

There is only simple DP. But you have to consider avenues 1 and 100 also, and remember that if you were said to divide it with 8 avenues, you have to output 8 avenues (even if the same optimal anser is for 4 )

I hope I will help you

Best regards

CYFRA

Can anyone provide some sample test data for me to test my program? I keep getting WA even though I'm pretty sure the program is correct.

Go to Waterloo contest website at http://plg.uwaterloo.ca/~acm00
and you will find all source codes and input datas.

But be sure not to spoil your "fun" by looking over solutions.

However, after I solve problems from Waterloo contest I always check out their solutions: they are quite impressive often.

1. Do Avenues run from South to North and Streets from West to East?
To put it simply, Avenues are vertical lines and Streets are horizontals, right?
2. "Riding" is a large rectangle we have obtained by S horizontal and A vertical cuts?

Maybe this part of task could be helpful for those of you, who get WA
"The city is bounded by four roads: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), 100th Avenue (north edge). Clearly these four roads must represent district boundaries;".

Maybe this part of task could be helpful for those of you, who get WA
"The city is bounded by four roads: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), 100th Avenue (north edge). Clearly these four roads must represent district boundaries;".

that's a useful hint