제출 #412136

#제출 시각아이디문제언어결과실행 시간메모리
412136SuhaibSawalha1카니발 티켓 (IOI20_tickets)C++17
14 / 100
670 ms63240 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; long long calc (vector<long long> &a) { int n = a.size(); long long sum = accumulate(a.begin(), a.end(), 0LL), m = LLONG_MAX, sum2 = 0; sort(a.begin(), a.end()); for (int i = 0; i < n; ++i) { sum -= a[i]; m = min(m, a[i] * i - sum2 + sum - a[i] * (n - i - 1)); sum2 += a[i]; } return m; } long long find_maximum(int k, vector<vector<int>> a) { long long ans = 0; int n = a.size(); int m = a[0].size(); vector<vector<int>> g(n, vector<int>(m, -1)); if (m == 1) { vector<long long> ask; g.assign(n, vector<int>(m, 0)); for (auto &e : a) { ask.push_back(e[0]); } return calc(ask); } vector<pair<int, array<vector<int>, 2>>> t; for (int i = 0; i < n; ++i) { array<vector<int>, 2> v; for (int j = 0; j < m; ++j) { v[a[i][j]].push_back(j); } t.push_back({i, v}); } #define zero(a) a.second[0].size() #define one(a) a.second[1].size() for (int kc = 0; kc < k; ++kc) { sort(t.begin(), t.end(), [&] (auto &a, auto &b) { return zero(a) > zero(b); }); int zeros = 0, ones = 0; for (int i = 0; i < (n + 1) / 2; ++i) { if (zero(t[i])) { ++zeros; g[t[i].first][t[i].second[0].back()] = kc; t[i].second[0].pop_back(); } else { ++ones; g[t[i].first][t[i].second[1].back()] = kc; t[i].second[1].pop_back(); } } for (int i = (n + 1) / 2; i < n; ++i) { if (one(t[i])) { ++ones; g[t[i].first][t[i].second[1].back()] = kc; t[i].second[1].pop_back(); } else { ++zeros; g[t[i].first][t[i].second[0].back()] = kc; t[i].second[0].pop_back(); } } ans += min(ones, zeros); } allocate_tickets(g); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...