제출 #1198692

#제출 시각아이디문제언어결과실행 시간메모리
1198692LucaLucaM카니발 티켓 (IOI20_tickets)C++20
100 / 100
583 ms62240 KiB
#include "tickets.h" #include <vector> #include <iostream> #include <algorithm> #include <cassert> using ll = long long; struct Change { int delta, i; 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; deltas.push_back({a[i][apare] + a[i][dispare], i}); } } std::sort(deltas.begin(), deltas.end()); assert((int) deltas.size() >= n * k / 2); for (int i = 0; i < n * k / 2; i++) { auto [increase, row] = deltas[i]; sum += increase; cntpos[row]++; cntneg[row]--; } 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++) { assert(cntpos[rows[i]] >= 0); answer[rows[i]][m - cntpos[rows[i]]--] = round; } for (int i = n / 2; i < n; i++) { assert(cntneg[rows[i]] >= 1); 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...