# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
66644 | Eae02 | 전선 연결 (IOI17_wiring) | C++14 | 1083 ms | 11896 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
struct Section
{
int connCount;
const int* connPositions;
uint64_t* memo;
};
std::vector<Section> sections;
uint64_t minLen(int sectIndex, int numWires)
{
const Section& section = sections[sectIndex];
if (section.memo[numWires] != 0)
return section.memo[numWires];
int toPrev = 0;
if (sectIndex > 0)
toPrev = section.connPositions[0] - sections[sectIndex - 1].connPositions[sections[sectIndex - 1].connCount - 1];
uint64_t lMin = UINT64_MAX;
if (sectIndex == sections.size() - 1)
{
lMin = (uint64_t)std::max(section.connCount - numWires, 0) * (uint64_t)toPrev;
for (int i = 0; i < section.connCount; i++)
{
lMin += section.connPositions[i] - section.connPositions[0];
}
}
else
{
int nextBegin = sections[sectIndex + 1].connPositions[0];
uint64_t lp = 0;
uint64_t ln = 0;
for (int i = 0; i < section.connCount; i++)
ln += nextBegin - section.connPositions[i];
for (int b = 0; true; b++)
{
if (lp + ln < lMin)
{
uint64_t l = lp + ln + minLen(sectIndex + 1, section.connCount - b);
lMin = std::min(lMin, l);
}
if (b == section.connCount || sectIndex == 0)
break;
ln -= nextBegin - section.connPositions[b];
lp += section.connPositions[b] - section.connPositions[0];
if (b >= numWires)
lp += toPrev;
}
}
section.memo[numWires] = lMin;
return lMin;
}
uint64_t g_memo[5000000];
long long min_total_length(std::vector<int> r, std::vector<int> b)
{
const int BLUE = 0;
const int RED = 1;
sections.reserve(r.size() + b.size());
int sectionColor = -1;
int ri = 0;
int bi = 0;
while (ri < r.size() || bi < b.size())
{
if ((ri == r.size() ? INT32_MAX : r[ri]) < (bi == b.size() ? INT32_MAX : b[bi]))
{
if (sectionColor != RED)
{
sections.emplace_back();
sections.back().connCount = 0;
sections.back().connPositions = &r[ri];
sectionColor = RED;
}
ri++;
}
else
{
if (sectionColor != BLUE)
{
sections.emplace_back();
sections.back().connCount = 0;
sections.back().connPositions = &b[bi];
sectionColor = BLUE;
}
bi++;
}
sections.back().connCount++;
}
uint64_t* memo = g_memo;
int maxWires = 0;
for (Section& section : sections)
{
section.memo = memo;
memo += maxWires + 1;
maxWires = section.connCount;
}
return minLen(0, 0);
}
컴파일 시 표준 에러 (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... |