# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
308054 | jwvg0425 | 카니발 티켓 (IOI20_tickets) | C++17 | 43 ms | 12776 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tickets.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#define all(x) x.begin(), x.end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
struct Ticket
{
int color;
int idx;
int value;
};
vector<ii64> small[1505];
vector<ii64> large[1505];
ii trace[85][10005];
i64 table[85][10005];
bool calc[85][10005];
int n, m;
i64 solve(int k, int idx, int scnt)
{
if (idx == n)
{
if (scnt == 0)
return 0;
else
return -(1ll << 60);
}
if (calc[idx][scnt])
return table[idx][scnt];
auto& res = table[idx][scnt];
calc[idx][scnt] = true;
int used = k * idx;
int sused = k * n / 2 - scnt;
int lused = used - sused;
int lcnt = k * n / 2 - lused;
for (int suse = 0; suse <= min(scnt, (int)small[idx].size()); suse++)
{
int luse = k - suse;
if (luse > lcnt || luse > large[idx].size())
continue;
i64 lv = (luse == 0) ? 0 : large[idx][luse - 1].yy;
i64 sv = (suse == 0) ? 0 : small[idx][suse - 1].yy;
i64 now = lv - sv + solve(k, idx + 1, scnt - suse);
if (now > res)
{
res = now;
trace[idx][scnt] = ii(suse, luse);
}
}
return res;
}
i64 find_maximum(int k, vector<vector<int>> x)
{
n = x.size();
m = x[0].size();
vector<Ticket> tickets;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
Ticket t;
t.color = i;
t.idx = j;
t.value = x[i][j];
tickets.push_back(t);
}
}
sort(all(tickets), [](const Ticket& l, const Ticket& r)
{
return l.value < r.value;
});
vector<vector<int>> ans(n, vector<int>(m, -1));
for (int l = 0; l < k * n / 2; l++)
{
int r = n * m - 1 - l;
small[tickets[l].color].emplace_back(tickets[l].idx, tickets[l].value);
large[tickets[r].color].emplace_back(tickets[r].idx, tickets[r].value);
}
for (int color = 0; color < n; color++)
{
for (int i = 1; i < small[color].size(); i++)
small[color][i].yy += small[color][i - 1].yy;
for (int i = 1; i < large[color].size(); i++)
large[color][i].yy += large[color][i - 1].yy;
}
i64 ret = solve(k, 0, k * n / 2);
int gidx = 0;
int cnt = k * n / 2;
for (int color = 0; color < n; color++)
{
for (int i = 0; i < trace[color][cnt].xx; i++)
{
ans[color][small[color][i].xx] = gidx;
gidx = (gidx + 1) % m;
}
int lgi = gidx;
for(int i =0; i < trace[color][cnt].yy;i++)
{
ans[color][large[color][i].xx] = lgi;
lgi = (lgi + 1) % m;
}
cnt -= trace[color][cnt].xx;
}
allocate_tickets(ans);
return ret;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |