#include "shortcut.h"
#include <bits/stdc++.h>
using ll = long long;
std::vector<ll> distBefore;
ll mainLineDist(int a, int b)
{
if (a > b)
std::swap(a, b);
if (a == b)
return 0;
return distBefore[b - 1] - ((a == 0) ? 0 : distBefore[a - 1]);
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
distBefore.resize(n - 1);
ll distAcc = 0;
for (int i = 0; i < l.size(); i++)
{
distAcc += l[i];
distBefore[i] = distAcc;
}
ll ans = INT64_MAX;
ll md0 = 0;
for (ll u = 0; u < n; u++)
{
for (ll v = u + 1; v < n; v++)
{
ll e = d[u] + d[v];
ll minThis = INT64_MAX;
minThis = std::min(minThis, mainLineDist(u, v) + e);
md0 = std::max(md0, minThis);
}
}
ans = std::min(ans, md0);
for (ll a = 0; a < n; a++)
{
for (ll b = a + 2; b < n; b++)
{
ll md = 0;
for (ll u = 0; u < n; u++)
{
for (ll v = u + 1; v < n; v++)
{
ll e = d[u] + d[v];
ll minThis = INT64_MAX;
minThis = std::min(minThis, mainLineDist(u, v) + e);
minThis = std::min(minThis, mainLineDist(u, a) + mainLineDist(v, b) + e + c);
minThis = std::min(minThis, mainLineDist(u, b) + mainLineDist(v, a) + e + c);
md = std::max(md, minThis);
}
}
ans = std::min(ans, md);
}
}
return ans;
}
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < l.size(); i++)
~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
356 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
2 ms |
432 KB |
n = 4, incorrect answer: jury 21 vs contestant 22 |
4 |
Halted |
0 ms |
0 KB |
- |