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 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

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

#include <iostream>
#include <cmath>
using namespace std;

long n;
long long s, a[200][15],res=-2147483647;
int main()
{
    long i,j,k,u;

    cin >> n;
    for (i=1; i<=n; i++)
        for (j=1; j<=11; j++)
            cin >> a[i][j];

    for (i=1; i<=n-2; i++)
        for (j=i+1; j<=n-1; j++ )
            for (k=j+1; k<=n; k++)
            {
                s=0;
                for (u=1; u<=11; u++)
                    s=s+max(a[i][u],max(a[j][u],a[k][u]));
                res=max(res,s);
            }
    cout << res;
    return 0;
}