F. CO-ABILITY
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 26 Accepted Submission(s) : 14
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
The Regional Contest is coming near, and all the acmers become very excited. As well as our coaches, they're very strategy, for they always think again and again how to select players , how to choose three players into one team and which team to assign to one or two of all sites… Such problems make their heads ached, including your coach, and he knows you're an excellent ACMer, so he's asking for your help. This is an easy problem for you, isn't it?
To make things easier, we make a little change. Assume that your organization has N ACMers, they're numbered from 1 to N.(It has nothing to do with their ability, just for the convenience of controlling). What's more, they're divided into N/2 teams, haha, which means one team has only 2 people, and if your organization has 5 ACMers, you could have at most 2 teams. I hope you would like such changes.
Teamwork is very important, when different two ACMers are combined into one team, they can have different co-ability. And now, given any two ACMers: i and j, your coach knows their co-ability (Pij). Here comes the problem, given all the Pij(1 <= i <= N,1 <= j <= N,0 < Pij<= 100), you should tell the most co-ability after all ACMers has their team can your school has.
To make things easier, we make a little change. Assume that your organization has N ACMers, they're numbered from 1 to N.(It has nothing to do with their ability, just for the convenience of controlling). What's more, they're divided into N/2 teams, haha, which means one team has only 2 people, and if your organization has 5 ACMers, you could have at most 2 teams. I hope you would like such changes.
Teamwork is very important, when different two ACMers are combined into one team, they can have different co-ability. And now, given any two ACMers: i and j, your coach knows their co-ability (Pij). Here comes the problem, given all the Pij(1 <= i <= N,1 <= j <= N,0 < Pij<= 100), you should tell the most co-ability after all ACMers has their team can your school has.
Input
The first line of the input is N(2<=N<=10 and N is an even number),the number of employees in the company.
Then there're N lines,each line has N numbers.The jth number in the ith line is Pij,as we discribe above.And we guarantee Pij = Pji,Pii = 0. The end-of-file is denoted by a single line containing the integer 0.
Then there're N lines,each line has N numbers.The jth number in the ith line is Pij,as we discribe above.And we guarantee Pij = Pji,Pii = 0. The end-of-file is denoted by a single line containing the integer 0.
Output
For each case,output the most profits this company can make.
Sample Input
4 0 6 62 13 6 0 35 94 62 35 0 5 13 94 5 0 0
Sample Output
156
Author
Source
developing schools contest 5