제출 #434603

#제출 시각아이디문제언어결과실행 시간메모리
434603frodakcin카니발 티켓 (IOI20_tickets)C++17
27 / 100
624 ms51644 KiB
#include "tickets.h" #include <vector> #include <numeric> #include <algorithm> #include <functional> using ll = long long; struct delta { public: int i, v; bool operator > (const delta& o) const {return v > o.v;} }; long long find_maximum(int K, std::vector<std::vector<int>> x) { int N = x.size(); int M = x[0].size(); std::vector<std::vector<int>> answer(N, std::vector<int>(M, -1)); ll ans=0; for(int i=0;i<N;++i) for(int j=0;j<K;++j) ans -= x[i][j]; std::vector<int> u(N, 0); std::vector<delta> gains; for(int i=0;i<N;++i) for(int j=0;j<K;++j) gains.push_back({i, x[i][M-j-1]+x[i][K-j-1]}); std::nth_element(gains.begin(), gains.begin()+(N*K/2), gains.end(), std::greater<delta>()); for(int i=0;i<N*K/2;++i) ++u[gains[i].i], ans += gains[i].v; // u = how many R we use std::vector<int> L(N, 0), R(N, M), ord(N); std::iota(ord.begin(), ord.end(), 0); for(int i=0;i<K;++i) { std::nth_element(ord.begin(), ord.begin()+N/2, ord.end(), [&](int x, int y){return u[x]<u[y];}); for(int j=0;j<N/2;++j) answer[ord[j]][L[ord[j]]++]=i; for(int j=N/2;j<N;++j) answer[ord[j]][--R[ord[j]]]=i, --u[j]; } allocate_tickets(answer); 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...