SHARE
TWEET

Untitled

a guest Sep 14th, 2017 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <string>
  6. #include <vector>
  7. #include <map>
  8. #include <set>
  9. #include <math.h>
  10. #include <numeric>
  11.  
  12. using namespace std;
  13.  
  14. struct Point {
  15.     int x, v;
  16.     bool operator < (Point obj) {
  17.         return this->x < obj.x;
  18.     }
  19. };
  20.  
  21. int main()
  22. {
  23. #if _DEBUG
  24.     freopen("input.txt", "r", stdin);
  25.     freopen("output.txt", "w", stdout);
  26. #endif
  27.     int caseTest = 0, n = 0, r = 0, k = 0;
  28.     vector<Point> vec;
  29.  
  30.     cin >> caseTest;
  31.     int caseCount = 1;
  32.     while (caseCount <= caseTest) {
  33.         //////////////////
  34.         cin >> n >> r >> k;
  35.         for (int i = 0; i < n; ++i) {
  36.             int tmp1 = 0, tmp2 = 0;
  37.             cin >> tmp1 >> tmp2;
  38.             Point p;
  39.             p.x = tmp1; p.v = tmp2;
  40.             vec.push_back(p);      
  41.         }
  42.         ////////////////////
  43.        
  44.         sort(vec.begin(), vec.end());      
  45.         std::vector<Point> vecUnique;
  46.  
  47.         for (int i = 0; i < vec.size() - 1; ++i) {
  48.             if (vec.at(i).x == vec.at(i + 1).x) {
  49.                 Point p;
  50.                 p.x = vec.at(i).x;
  51.                 p.v = vec.at(i).v + vec.at(i + 1).v;
  52.                 vecUnique.push_back(p);
  53.                 ++i;
  54.             }
  55.             else {
  56.                 vecUnique.push_back(vec.at(i));
  57.             }
  58.             if ((i + 1 == vec.size() - 1) && vec.at(i + 1).x != vec.at(i).x) {
  59.                 vecUnique.push_back(vec.at(i + 1));
  60.             }          
  61.         }
  62.  
  63.         int maxPunch = INT_MIN;
  64.         vector<int> punches;
  65.         bool isNew;
  66.         for (int i = 0; i < k; ++i) {
  67.             int f1 = 0, f2 = 0;
  68.             for (int i = 0; i < vecUnique.size() - 1; ++i) {
  69.                 if (vecUnique.at(i).x != vecUnique.at(i + 1).x) {
  70.                     maxPunch = INT_MIN;
  71.                     if (ceil(((vecUnique.at(i + 1).x - vecUnique.at(i).x) / 2.0)) <= r) {
  72.                         if (vecUnique.at(i + 1).v + vecUnique.at(i).v > maxPunch) {
  73.                             f1 = i;
  74.                             f2 = i + 1;
  75.                             maxPunch = vecUnique.at(i + 1).v + vecUnique.at(i).v;
  76.                             isNew = true;
  77.                         }
  78.                     }
  79.                 }
  80.             }
  81.             if (isNew) {
  82.                 vecUnique.erase(vecUnique.begin() + f1, vecUnique.begin() + f2 + 1);
  83.                 isNew = false;
  84.             }
  85.            
  86.             punches.push_back(maxPunch);           
  87.         }
  88.         int sum_of_elems = std::accumulate(punches.rbegin(), punches.rbegin() + k, 0);
  89.         cout << "Case " << caseCount << ": " <<sum_of_elems << endl;
  90.         vec.clear();
  91.         ++caseCount;
  92.     }
  93.    
  94.     return 0;
  95. }
RAW Paste Data
Top