Submission #1198690

#TimeUsernameProblemLanguageResultExecution timeMemory
1198690LucaLucaM카니발 티켓 (IOI20_tickets)C++20
16 / 100
309 ms51328 KiB
#include "tickets.h" #include <vector> #include <iostream> #include <algorithm> using ll = long long; struct Change { int delta, i, j; bool operator < (const Change &other) const { return delta > other.delta; }; }; ll find_maximum(int k, std::vector<std::vector<int>> a) { int n = (int) a.size(); int m = (int) a[0].size(); std::vector<std::vector<int>> answer(n, std::vector<int>(m, -1)); std::vector<int> cntneg(n, k); std::vector<int> cntpos(n, 0); ll sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { sum += -a[i][j]; } } std::vector<Change> deltas; for (int i = 0; i < n; i++) { for (int alcatelea = 1; alcatelea <= k; alcatelea++) { int apare = m - alcatelea; int dispare = k - alcatelea; if (apare < k) { break; } deltas.push_back({a[i][apare] + a[i][dispare], i, apare}); } } std::sort(deltas.begin(), deltas.end()); for (int i = 0; i < n * k / 2; i++) { auto [increase, row, apare] = deltas[i]; sum += increase; cntpos[row]++; cntneg[row]--; } std::vector<int> pozitive = cntpos; std::vector<int> negative = cntneg; for (int round = 0; round < k; round++) { std::vector<int> rows; for (int i = 0; i < n; i++) { rows.push_back(i); } std::sort(rows.begin(), rows.end(), [&](int x, int y) { return cntpos[x] > cntpos[y]; }); for (int i = 0; i < n / 2; i++) { answer[rows[i]][m - cntpos[rows[i]]--] = round; } for (int i = n / 2; i < n; i++) { answer[rows[i]][--cntneg[rows[i]]] = round; } } allocate_tickets(answer); return sum; }
#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...