HCN3D - The God-land
English | Tiếng Việt |
How great is our God! To show the respect for God, Bethlehem people decide to build a large area for memorial called "The God-land". There's a story that God used to visit N areas which is rectangles having edges paralell to the axises, described by the co-ordinate of a pair of opposite vertices: Xi1, Yi1, Xi2, Yi2 (any two of them may have no common point, one common vertex or one common edge at most); on which of them there is a kind of grass called Ci. People there want to build the God-land which is also a rectangle having edges parallel to the axises, putting on area(s) mentioned above, having a same kind of grass and having the maximum area! Help them to find the God-land before this Christmas!
Input
- The first line contains N.
- Next N line(s), each line contains Xi1, Yi1, Xi2, Yi2 and Ci describing the ith area to which God used to visit.
Output
- The maximum area found.
Sample
Input:
5
1 1 3 3 1
3 1 5 3 1
1 4 3 6 1
3 4 5 6 1
0 3 6 4 2
Output:
8
Input:
5
5 5 6 6 22
3 4 6 5 22
6 3 7 6 22
5 6 8 7 22
4 5 5 8 22
Output:
9
Limitations
- N ≤ 2500.
- 0 ≤ Xi1, Yi1, Xi2, Yi2 ≤ 109.
- 1 ≤ Ci ≤ 100.
Sorry for my bad English!^_^ Please comment for a better translation ;)
hide comments
AnhDQ:
2009-05-24 00:53:04
sorry, im a newbie so i dont know the differences much:d |
|
Robert Gerbicz:
2009-05-24 00:53:04
Moved it back to classical. Why would it be a challenge? |
|
AnhDQ:
2009-05-24 00:53:04
Input has no 0-area rectangle! and if you ask why your submit results 0, its WA all test cases ;) Last edit: 2009-05-07 15:47:12 |
|
ufuk altunbulak:
2009-05-24 00:53:04
What does it mean result=0 |
|
AnhDQ:
2009-05-24 00:53:04
Updated Time limit! enjoy! |
|
[Trichromatic] XilinX:
2009-05-24 00:53:04
Time limit too strict. |
Added by: | AnhDQ |
Date: | 2009-05-02 |
Time limit: | 0.200s-0.800s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | AnhDQ (re-coverd) |