Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBSELECT - VOI06 Chọn ô

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbselect


Cho một bảng hình chữ nhật kích thước 4×n ô vuông. Các dòng được đánh số từ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên mỗi ô (i,j) có ghi một số nguyên aij , i =1, 2, 3, 4; j =1, 2, ..., n. Một cách chọn ô là việc xác định một tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ô nào trong S có chung cạnh. Các ô trong tập S được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn. Tìm cách chọn sao cho trọng lượng là lớn nhất.

Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây:

Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lượng 32.

Input

Dòng đầu tiên chứa số nguyên dương n là số cột của bảng.

Cột thứ j trong số n cột tiếp theo chứa 4 số nguyên a1j, a2j, a3j, a4j, hai số liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng.

Output

Gồm 1 dòng duy nhất là trọng lượng của cách chọn tìm được.

Example

Input:
3
-1 9 3
-4 5 -6
7  8 9
9  7 2

Output:
32

Hạn chế

Trong tất cả các test: n ≤ 10000, |aij| ≤ 30000. Có 50% số lượng test với n ≤ 1000.


Được gửi lên bởi:special_one
Ngày:2008-09-25
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Vietnam Olympiad of Informatics 2006 - Bảng B

hide comments
2014-09-06 14:28:05 ■■‡[ND] Bee Sociu■■‡
Ngon =)))))
2014-08-24 16:59:39 [$Zeus$]
mình quên phải lấy 1 tập 'khác rỗng' nên đc 94.12 điểm... haizz

Last edit: 2014-08-24 16:59:57
2014-08-16 11:37:35 Messi_CBH
why? 94.12
2014-07-11 11:27:20 1 ðấm AC
đấm phát chết luôn :v
2013-12-18 05:19:22 Nguyễn Hoàng Nam
test vớ vẩn ghê. thế khi hết dòng một thì dòng dưới vẫn là a[1,i] hay là a[2] rồi. zzz
2013-05-27 07:20:35 a;slkfjasl;fkj
bài này mình làm một hồi được 5.88
Sau đó cố gắng hết sức đã được 94.12
=> 5.88+94.12=100 => coi như mình đã AC :))
2013-04-03 16:48:30 Chuyên Triết Tổng Hợp
trạng thái :3
2012-12-21 14:53:47 Nguyễn Thái Cường
Lưu ý có test toàn số âm thì chọn 1 ô lớn nhất :D
2012-11-21 17:56:34 Nguyễn Thái Cường
94.12 , ko hiểu @@
2012-01-09 08:02:01 Lê Trường Giang
94.12 @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.