algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }