VOI 06 Bài 1 - Chọn ô

View as PDF

Submit solution


Points: 0.12 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Vietnam Olympiad of Informatics 2006 - Bảng B
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 ~a_{i,j}~, ~i = 1, 2, 3, 4;~ ~j = 1, 2, \dots, 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:

image

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 ~a_{1,j}~ , ~a_{2j,}~ , ~a_{3,j}~ , ~a_{4,j}~, 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.

Giới hạn

Trong tất cả các test: ~n \leq 10\,000~, ~|a_{i,j}| \leq 30\,000~.

Có 50% số lượng test với ~n \leq 1000~.

Sample Input

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

Sample Output

32

Comments

Please read the guidelines before commenting.



  • 0
    phannam310810  commented on May 10, 2025, 3:30 p.m.

    mmb


  • 1
    Thanh09  commented on April 1, 2025, 7:01 a.m. edited

    ban em comment, em xin loi moi nguoi a...


    • -5
      tiendungnguyen860  commented on April 1, 2025, 8:47 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -2
      kqhuy123  commented on April 1, 2025, 8:42 a.m.

      cẩn thận bị ban nha bạn


    • -4
      ThanhPhong  commented on April 1, 2025, 7:10 a.m.

      tuc tiu qua, thu hoi tin nhan di b


  • -3
    ThanhBC1234  commented on Feb. 24, 2025, 7:47 a.m. edited

    dp bitmask


  • -3
    minhtuanvp2011  commented on Feb. 23, 2025, 3:51 p.m.

    dp bitmark


  • -6
    nehuy7410  commented on Nov. 28, 2024, 12:50 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 24
    huynhquocluatit10  commented on April 13, 2024, 8:48 a.m. edited

    gợi ý:có trường hợp full âm nha


    • -1
      minha2k25cvp  commented on Oct. 9, 2024, 2:58 p.m.

      bạn có test khong ạ, mình vãn bị sai 1 test


    • -5
      duonggiabao2008  commented on April 13, 2024, 8:52 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -61
    tonblan  commented on March 17, 2024, 6:15 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -15
      hieuhfgr  commented on March 19, 2024, 8:21 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -32
    nogo007akapkn  commented on Nov. 8, 2023, 2:28 a.m. edit 3

    This comment is hidden due to too much negative feedback. Show it anyway.