| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 419363 | cpp219 | 카니발 티켓 (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include "tickets.h"
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1500 + 9;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
long long kq;
ll n,m,k;
multiset<LL> ms[N];
set<LL> sMin,sMax; /// val id
void Repack(){
sMin.clear(); sMax.clear();
for (ll i = 0;i < n;i++){
LL L = *ms[i].begin(),R = *ms[i].rbegin();
sMin.insert({L.fs,i});
sMax.insert({R.fs,i});
}
}
long long find_maximum(ll k, vector<vector<ll>> a){
n = a.size();
for (ll i = 0;i < n;i++){
for (ll j = 0;j < a[i].size();j++){
ll now = a[i][j];
ms[i].insert({now,j});
}
}
Repack();
ll ans[N][N]; memset(ans,-1,sizeof(ans));
for (ll id = 1;id <= k;id++){
ll big,sm;
ll take = n/2;
while(take--){
LL p = *sMax.rbegin(); sMax.erase(p);
LL now = *ms[p.sc].rbegin(); ms[p.sc].erase(*ms[p.sc].rbegin());
ans[p.sc][now.sc] = id; big = p.fs;
LL cur = *ms[p.sc].begin();
cur.sc = p.sc; sMin.erase(cur);
//cout<<cur.fs<<" "<<cur.sc<<" x ";
//cout<<sMax.size()<<" "<<sMin.size()<<"\n\n";
p = *sMin.begin(); sMin.erase(p);
now = *ms[p.sc].begin(); ms[p.sc].erase(ms[p.sc].begin());
ans[p.sc][now.sc] = id; sm = p.fs; //cout<<p.sc<<"\n";
cur = *ms[p.sc].rbegin();
cur.sc = p.sc; sMax.erase(cur);
//cout<<big<<" "<<sm<<"\n";
kq += (long long) big - sm;
}
Repack(); //exit(0);
}
allocate_tickets(ans);
return kq;
}