Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include "optimization.h"
- using namespace std;
- #define INFILE "input.txt"
- #define OUTFILE "output.txt"
- void Partition(int l, int r, pair<int, int> x, vector<pair<int, int>> & a, int& i, int& j) {
- vector<pair<int, int>> lss;
- vector<pair<int, int>> mid;
- vector<pair<int, int>> more;
- for (int i = l; i < r; ++i) {
- if (a[i].second == x.second) {
- mid.push_back(a[i]);
- } else
- if (a[i].second < x.second) {
- lss.push_back(a[i]);
- } else {
- more.push_back(a[i]);
- }
- }
- int index = l;
- for (; index - l < lss.size(); ++index) {
- a[index] = lss[index - l];
- }
- j = index;
- for (; index - l < mid.size() + lss.size(); ++index) {
- a[index] = mid[index - lss.size() - l];
- }
- i = index;
- for (; index - l < more.size() + lss.size() + mid.size(); ++index) {
- a[index] = more[index - l - mid.size() - lss.size()];
- }
- }
- int Stat(int64_t k, int l, int r, vector<pair<int, int>> & a) {
- if (r - l < 1) return 0;
- if (r - l == 1) return a[l].second;
- int i = l, j = r;
- int pivot = l + (r - l) / 2;
- Partition(l, r, a[pivot], a, i, j);
- int64_t sum = 0;
- for (int t = 0; t < j; ++t) {
- sum += a[t].first;
- }
- int64_t sumd = sum;
- for (int t = j; t < i; t++)
- {
- sumd += a[t].first;
- }
- if (2 * sum > k && j - l > 0) {
- return Stat(k, l, j, a);
- } else
- if (2 * sumd > k){
- return a[j].second;
- } else {
- return Stat(k, i, r, a);
- }
- }
- int main() {
- freopen (INFILE, "r", stdin);
- freopen (OUTFILE, "w", stdout);
- unsigned int t, n;
- unsigned int halfN;
- t = readInt();
- for (int i = t; i > 0; --i) {
- n = readInt();
- vector<pair<int, int>> Z;
- vector<pair<int, int>> T;
- vector<int> weights;
- vector<int> xs;
- vector<int> ys;
- int64_t half_weight = 0;
- for (int j = 0; j < n; ++j) {
- int x = readInt();
- int y = readInt();
- int w = readInt();
- xs.push_back(x);
- ys.push_back(y);
- weights.push_back(w);
- half_weight += w;
- Z.push_back(make_pair(w, x + y));
- T.push_back(make_pair(w, x - y));
- }
- int z_index = Stat(half_weight, 0, n, Z);
- int t_index = Stat(half_weight, 0, n, T);
- int X = (z_index + t_index);
- int Y = (z_index - t_index);
- int64_t sum_time = 0;
- for (int k = 0; k < n; ++k) {
- sum_time += weights[k] * max(abs(2 * xs[k] - X), abs(2 * ys[k] - Y));
- }
- writeInt(sum_time, '\n');
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement