Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <map>
- #include <set>
- #include <math.h>
- #include <numeric>
- using namespace std;
- struct Point {
- int x, v;
- bool operator < (Point obj) {
- return this->x < obj.x;
- }
- };
- int main()
- {
- #if _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int caseTest = 0, n = 0, r = 0, k = 0;
- vector<Point> vec;
- cin >> caseTest;
- int caseCount = 1;
- while (caseCount <= caseTest) {
- //////////////////
- cin >> n >> r >> k;
- for (int i = 0; i < n; ++i) {
- int tmp1 = 0, tmp2 = 0;
- cin >> tmp1 >> tmp2;
- Point p;
- p.x = tmp1; p.v = tmp2;
- vec.push_back(p);
- }
- ////////////////////
- sort(vec.begin(), vec.end());
- std::vector<Point> vecUnique;
- for (int i = 0; i < vec.size() - 1; ++i) {
- if (vec.at(i).x == vec.at(i + 1).x) {
- Point p;
- p.x = vec.at(i).x;
- p.v = vec.at(i).v + vec.at(i + 1).v;
- vecUnique.push_back(p);
- ++i;
- }
- else {
- vecUnique.push_back(vec.at(i));
- }
- if ((i + 1 == vec.size() - 1) && vec.at(i + 1).x != vec.at(i).x) {
- vecUnique.push_back(vec.at(i + 1));
- }
- }
- int maxPunch = INT_MIN;
- vector<int> punches;
- bool isNew;
- for (int i = 0; i < k; ++i) {
- int f1 = 0, f2 = 0;
- for (int i = 0; i < vecUnique.size() - 1; ++i) {
- if (vecUnique.at(i).x != vecUnique.at(i + 1).x) {
- maxPunch = INT_MIN;
- if (ceil(((vecUnique.at(i + 1).x - vecUnique.at(i).x) / 2.0)) <= r) {
- if (vecUnique.at(i + 1).v + vecUnique.at(i).v > maxPunch) {
- f1 = i;
- f2 = i + 1;
- maxPunch = vecUnique.at(i + 1).v + vecUnique.at(i).v;
- isNew = true;
- }
- }
- }
- }
- if (isNew) {
- vecUnique.erase(vecUnique.begin() + f1, vecUnique.begin() + f2 + 1);
- isNew = false;
- }
- punches.push_back(maxPunch);
- }
- int sum_of_elems = std::accumulate(punches.rbegin(), punches.rbegin() + k, 0);
- cout << "Case " << caseCount << ": " <<sum_of_elems << endl;
- vec.clear();
- ++caseCount;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement