No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
Time limit per test: 0.5 second(s)

Memory limit: 65536 kilobytes

Memory limit: 65536 kilobytes

input: standard

output: standard

output: standard

The restoration of the old Berland railroad has been finished at last. From above the railroad has the form of the polyline possibly with self-intersections but without self-covering. All segments of the polyline are either parallel or perpendicular to the earth equator line, which is considered to be a straight line.

Ministers now have a very difficult task. They have to determine the length of the train traveling back and forth. The decision was made to minimize the fuel expenses. To achieve this goal the length of the train should be maximal. There and then the assumption was made that the length of the train should be equal to the length of the railroad. In this case the fuel expenses will be equal to zero. The problem is that the train cannot have any self-intersections and self-touchings at any moment of time, although the head and the tail can occupy the same point. That's why the length of the train should possibly be reduced. Your task is to find the maximum possible length of the train. You can neglect the width of the rails and consider it equals to zero.

sample input | sample output |

5 0 0 3 0 3 1 1 1 1 -1 | 6 |

sample input | sample output |

7 0 0 1 0 1 1 3 1 3 0 1 0 1 -1 | 6 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 19:12:15 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|