02/10/2018, 15:02

PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC

Nguồn đề bài: http://vn.spoj.com/PTIT/problems/PTIT016E/ 1. Đề bài PTIT016E spoj Kỳ thi ACM/ICPC được tổ chức giữa các trường đại học ở Việt Nam. Mỗi trường sẽ chọn ra một đội gồm 3 thí sinh để thi đấu. Để chuẩn bị tốt cho kỳ thi, trường XYZ đã có kế hoạch tập huấn cho sinh viên ...

Nguồn đề bài: http://vn.spoj.com/PTIT/problems/PTIT016E/

1. Đề bài PTIT016E spoj

Kỳ thi ACM/ICPC được tổ chức giữa các trường đại học ở Việt Nam. Mỗi trường sẽ chọn ra một đội gồm 3 thí sinh để thi đấu. Để chuẩn bị tốt cho kỳ thi, trường XYZ đã có kế hoạch tập huấn cho  sinh viên với  chủ đề:

  1. Lý thuyết độ phức tạp tính toán
  2. Tổ hợp và số học
  3. Sắp xếp, tìm kiếm nâng cao
  4. Xử lý xâu
  5. Quy hoạch động
  6. Duyệt toàn bộ và nhánh cận
  7. Các thuật toán đồ thị
  8. Các thuật toán xấp xỉ
  9. Các thuật toán hình học
  10. Lý thuyết trò chơi
  11. Một số cấu trúc dữ liệu nâng cao

Kết thúc khoá tập huấn, Ban giám hiệu đã thống kê khả năng của từng sinh viên và muốn chọn ra 3 sinh viên để lập thành đội đi thi với hi vọng đạt kết quả cao nhất. Giả sử s[i][j] là điểm đánh giá khả năng của sinh viên  với chủ đề  thì việc đánh giá khả năng đạt kết quả cao của đội gồm 3 thí sinh x, y, z bằng max(s[x][1], s[y][1], s[z][1]) + max(s[x][2], s[y][2], s[z][2]) + … + max(s[x][11], s[y][11], s[z][11]).

Yêu cầu: Cho n sinh viên và s[i][j] là khả năng của sinh viên i với chủ đề j, hãy giúp Ban giám hiệu trường chọn ra 3 sinh viên thành một đội thi đấu có khả năng đạt kết quả cao nhất.

Input

Dòng đầu tiên chứa số nguyên n (n≤100).
n dòng tiếp theo, mỗi dòng chứa 11 số nguyên không âm s_(i,j)  (s_(i,j)≤〖10〗^9)
Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.
    Dòng đầu tiên chứa số nguyên n (n≤100).
n dòng tiếp theo, mỗi dòng chứa 11 số nguyên không âm s[i][j] (s[i][j] <= 10^9)
Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

• Khả năng đạt kết quả cao nhất của đội có 3 thí sinh được chọn.

Example

Input:
4
2 2 2 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0
1 3 1 0 0 0 0 0 0 0 0
1 1 3 0 0 0 0 0 0 0 0

Output:
9

2. Code PTIT016E spoj PTIT – ACM PTIT 2016

0