제출 #304129

#제출 시각아이디문제언어결과실행 시간메모리
304129QAQAutoMaton카니발 티켓 (IOI20_tickets)C++17
0 / 100
1 ms640 KiB
#include "tickets.h" #include <bits/stdc++.h> typedef std::pair<int,int> pii; #define x first #define y second std::vector<pii> vt[1505]; int cur[1505],id[1505]; std::priority_queue<pii> pq; void Push(int x,int k,int m){ if(cur[x]>k)return; pq.push(std::make_pair(vt[x][k-cur[x]].x+vt[x][m-cur[x]].x,x)); } std::vector<int> vd[1505],va[1505]; long long find_maximum(int k, std::vector<std::vector<int>> a) { int n = a.size(); int m = a[0].size(); std::vector<std::vector<int>> answer(n,std::vector<int>(m,-1)); int ans=0; for(int i=0;i<n;++i){ vt[i].resize(m); for(int j=0;j<m;++j)vt[i][j]=std::make_pair(a[i][j],j); std::sort(vt[i].begin(),vt[i].end()); for(int j=0;j<k;++j){ans-=vt[i][j].x;} cur[i]=1; Push(i,k,m); } int w=(n>>1)*k,hn=n>>1; for(int i=0;i<w;++i){ ans+=pq.top().x; int id=pq.top().y; pq.pop(); ++cur[id]; Push(i,k,m); } for(int i=0;i<n;++i){ for(int j=0;j<=k-cur[i];++j)vd[i].emplace_back(vt[i][j].y); for(int j=m-cur[i]+1;j<m;++j)va[i].emplace_back(vt[i][j].y); id[i]=i; } for(int i=0;i<k;++i){ std::sort(id,id+n,[](int x,int y){return vd[x].size()<vd[y].size();}); for(int j=0;j<hn;++j){ answer[id[j]][va[id[j]].back()]=i; va[id[j]].pop_back(); } for(int j=hn;j<n;++j){ answer[id[j]][vd[id[j]].back()]=i; vd[id[j]].pop_back(); } } 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...