t1.cpp (1494B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_map> 4 5 int square(int x) { 6 return x * x; 7 } 8 9 int solve(std::vector<int> nums) { 10 11 int sum = 0; 12 13 while(nums.size() > 0) { 14 15 std::unordered_map<int,int> priors {}; 16 std::pair<int,int> bestIndexPair; 17 int bestScore = 0; 18 19 for(int i = 0; i < nums.size(); ++i) { 20 if(priors.find(nums[i]) == priors.end()) { 21 priors[nums[i]] = i; 22 } 23 int firstIdx = priors[nums[i]]; 24 int score = square((i - firstIdx) + 1); 25 if(score > bestScore) { 26 bestScore = score; 27 bestIndexPair = {firstIdx,i}; 28 } 29 } 30 31 std::vector<int> next {}; 32 33 for(int i = 0; i < nums.size(); ++i) { 34 if(i >= bestIndexPair.first && i <= bestIndexPair.second) { 35 continue; 36 } else { 37 next.push_back(nums[i]); 38 } 39 } 40 41 sum += bestScore; 42 nums = next; 43 } 44 45 return sum; 46 47 } 48 49 int main() { 50 // greedily select the highest score first, in any order for ties 51 int caseCount, numCount, current; 52 std::cin >> caseCount; 53 for(int i = 0; i < caseCount; ++i) { 54 std::cin >> numCount; 55 numCount *= 2; 56 std::vector<int> nums {}; 57 for(int x = 0; x < numCount; ++x) { 58 std::cin >> current; 59 nums.push_back(current); 60 } 61 std::cout << solve(nums) << std::endl; 62 } 63 }