| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1022376 | Cyber_Wolf | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Problem: P3 - Carnival Tickets
// Contest: DMOJ - IOI '20
// URL: https://dmoj.ca/problem/ioi20p3
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include "tickets.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
long long find_maximum(int k, vector<vector<int>> V)
{
int n = V.size();
int m = V[0].size();
vector<vector<array<lg, 2>>> v;
lg ans = 0;
vector<array<lg, 4>> o;
auto a = V;
for(int i = 0; i < n; i++)
{
v.push_back({});
for(int j = 0; j < m; j++)
{
v[i].push_back({V[i][j], j});
a[i][j] = -1;
}
}
vector<int> neg[n], pos[n];
for(int i = 0; i < n; i++)
{
sort(v[i].begin(), v[i].end());
for(int j = 0; j < k; j++)
{
ans -= v[i][j][0];
o.push_back({v[i][m-k+j][0]+v[i][j][0], i, v[i][j][1], v[i][m-k+j][1]});
}
}
vector<array<int, 2>> npos(n);
for(int i = 0; i < n; i++) npos[i] = {0, i};
sort(o.rbegin(), o.rend());
for(int i = 0; i < n*k/2; i++)
{
ans += o[i][0];
pos[o[i][1]].push_back(o[i][3]);
npos[o[i][1]][0]++;
}
for(int i = n*k/2; i < n*k; i++)
{
neg[o[i][1]].push_back(o[i][2]);
}
for(int i = 0; i < k; i++)
{
sort(npos.begin(), npos.end());
//negatives
for(int j = 0; j < n/2; j++)
{
a[npos[j][1]][neg[npos[j][1]].back()] = i;
neg[npos[j][1]].pop_back();
}
//positives
for(int j = n/2; j < n; j++)
{
a[npos[j][1]][pos[npos[j][1]].back()] = i;
pos[npos[j][1]].pop_back();
npos[j][0]--;
}
}
allocate_tickets(a);
return ans;
}
/*
*/
int main()
{
fastio;
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> v;
for(int i = 0; i < n; i++)
{
v.push_back({});
for(int j = 0; j < m; j++)
{
int x;
cin >> x;
v[i].push_back(x);
}
}
cout << find_maximum(k, v) << '\n';
return 0;
}