Submission #623558

#TimeUsernameProblemLanguageResultExecution timeMemory
623558JeanBombeurCarnival Tickets (IOI20_tickets)C++17
14 / 100
457 ms67404 KiB
#include "tickets.h" #include <vector> #include <algorithm> using namespace std; // <|°_°|> // M. Broccoli const int MAX_COLORS = (1500); long long Optimal[MAX_COLORS * MAX_COLORS]; int NbSmall[MAX_COLORS]; long long find_maximum(int nbRounds, vector <vector <int>> Tickets) { int nbColors = Tickets.size(); int nbTickets = Tickets[0].size(); vector <vector <int>> Answer; long long answer = 0; for (int i = 0; i < nbColors; i ++) { for (int j = 0; j < nbRounds; j ++) { Optimal[nbRounds * i + j] = ((Tickets[i][j] + Tickets[i][j + nbTickets - nbRounds]) << 11) + i; answer += Tickets[i][j + nbTickets - nbRounds]; } } sort(Optimal, Optimal + nbColors * nbRounds); for (int i = 0; i < (nbColors * nbRounds) / 2; i ++) { NbSmall[Optimal[i] & ((1 << 11) - 1)] ++; answer -= Optimal[i] >> 11; } int cnt = 0; vector <int> row(nbTickets, -1); for (int i = 0; i < nbColors; i ++) { for (int j = 0; j < nbTickets; j ++) { row[j] = -1; } for (int j = 0; j < NbSmall[i]; j ++) { row[j] = cnt ++; if (cnt == nbRounds) cnt = 0; } for (int j = 0; j < nbRounds - NbSmall[i]; j ++) { row[nbTickets - j - 1] = cnt + j >= nbRounds ? cnt + j - nbRounds : cnt + j; } Answer.push_back(row); } allocate_tickets(Answer); return answer; }
#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...