| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 421683 | 2021-06-09T10:53:16 Z | idk321 | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KB |
#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000000LL;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
answer.resize(n, vector<int>(m, -1));
if (m == 1)
{
for (int i = 0; i < n; i++) answer[i][0] = 0;
allocate_tickets(answer);
vector<int> values(n);
for (int i = 0; i < n; i++)
{
values[i] = x[i][0];
}
sort(values.begin(), values.end());
ll res = 0;
int mid = (0 + n - 1) / 2;
for (int i = 0; i < n; i++)
{
res += abs(values[mid] - values[i]);
}
return res;
}
vector<vector<array<int, 2>>> valAndInd.resize(n, vector<array<int, 2>(m));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
valAndInd[i][j] = {x[i][j], j};
}
}
for (int i = 0; i < n; i++) sort(valAndInd[i].begin(), valAndInd[i].end());
int big = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++) big = max(big, x[i][j]);
}
if (big <= 1)
{
int turn = 0;
int res = 0;
for (int j = 0; j < m; j++)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += valAndInd[i][j][0];
}
if (sum == 0)
{
for (int i = 0; i < n; i++)
{
answer[i][valAndInd[i][j][1]] = turn;
}
turn++;
}
if (sum == n)
{
for (int i = 0; i < n; i++)
{
answer[i][valAndInd[i][j][1]] = turn;
}
turn++;
}
if (turn == k) break;
}
int cur = 0;
for (int i = 0; i < n, turn < k; i++)
{
for (int j = 0; j < m, turn < k; j++)
{
if (answer[i][j] == -1)
{
answer[i][j] = turn;
cur++;
if (cur == n)
{
turn++;
}
}
}
}
allocate_tickets(answer);
return res;
}
/*
if (k == 1)
{
array<int, 3> best = {-1, -1, -1};
vector<array<int, 2>> byVal;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
byVal.push_back({x[i][j], i});
}
}
sort(byVal.begin(), byVal.end());
vector<array<int, 2>> order;
for (int i = 0; i < n; i++)
{
order.push_back({x[i].front(), i});
}
ll cres = 0;
for (int i = 0; i < n; i++)
{
cres += x[i].back() - byVal[0][0];
}
ll res = INF;
int take = 0;
for (auto val : byVal)
{
int num = val[0];
while (take < n && order[take].front() <= num)
{
cres -=
take++;
}
}
} */
return 1;
}