Submission #2560285
Source Code Expand
#include <limits>
using ll = long long;
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr ll LNF = std::numeric_limits<ll>::max() / 2;
#include <bits/stdc++.h>
using namespace std;
struct edge {
ll cost;
int to;
};
bool operator<(const edge &lhs, const edge &rhs) {
return lhs.cost < rhs.cost;
}
bool operator>(const edge &lhs, const edge &rhs) {
return rhs.cost < lhs.cost;
}
struct queue_node {
ll cost;
int from;
};
bool operator<(const queue_node &lhs, const queue_node &rhs) {
return lhs.cost < rhs.cost;
}
bool operator>(const queue_node &lhs, const queue_node &rhs) {
return rhs.cost < lhs.cost;
}
struct result_node {
ll cost;
int step;
};
bool operator<(const result_node &lhs, const result_node &rhs) {
return lhs.cost < rhs.cost;
}
bool operator>(const result_node &lhs, const result_node &rhs) {
return rhs.cost < lhs.cost;
}
vector<result_node> dijkstra(vector<vector<edge>> const &graph, int start,
int step_limit) {
vector<result_node> result(graph.size(), {LNF, 0});
priority_queue<queue_node, vector<queue_node>, greater<queue_node>> que;
result[start] = {0, 0};
que.push({0, start});
while (!que.empty()) {
auto c = que.top();
que.pop();
// if (c.cost > result[c.from].cost) continue;
for (auto e : graph[c.from]) {
if (result[e.to].cost > result[c.from].cost + e.cost &&
result[c.from].step < step_limit) {
result[e.to].cost = result[c.from].cost + e.cost;
result[e.to].step = result[c.from].step + 1;
que.push({result[e.to].cost, e.to});
}
}
}
return result;
}
int main() {
int N;
ll x;
cin >> N >> x;
vector<vector<edge>> graph(N + 1);
for (int i = 0; i < N; i++) {
ll cost;
cin >> cost;
graph[0].push_back({cost, i + 1});
graph[(i + (N - 1)) % N + 1].push_back({0, i + 1});
}
ll cand = LNF;
for (int limit = 1; limit <= N; limit++) {
auto result = dijkstra(graph, 0, limit);
auto max_steps = accumulate(
result.begin(), result.end(), 0,
[](auto const &s, auto const &a) { return max(s, a.step); });
max_steps--;
// cerr << max_steps << endl;
auto sum_summon = accumulate(
result.begin() + 1, result.end(), 0ll,
[&](auto const &s, auto const &a) { return s + a.cost; });
cand = min(cand, sum_summon + x * max_steps);
}
cout << cand << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Colorful Slimes |
User |
statiolake |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2709 Byte |
Status |
WA |
Exec Time |
605 ms |
Memory |
512 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
237 ms |
512 KB |
1_01.txt |
AC |
238 ms |
512 KB |
1_02.txt |
AC |
238 ms |
512 KB |
1_03.txt |
AC |
237 ms |
512 KB |
1_04.txt |
AC |
389 ms |
512 KB |
1_05.txt |
AC |
390 ms |
512 KB |
1_06.txt |
AC |
529 ms |
512 KB |
1_07.txt |
AC |
530 ms |
512 KB |
1_08.txt |
AC |
371 ms |
512 KB |
1_09.txt |
AC |
371 ms |
512 KB |
1_10.txt |
AC |
445 ms |
512 KB |
1_11.txt |
AC |
594 ms |
512 KB |
1_12.txt |
WA |
539 ms |
512 KB |
1_13.txt |
AC |
366 ms |
384 KB |
1_14.txt |
WA |
595 ms |
512 KB |
1_15.txt |
WA |
458 ms |
512 KB |
1_16.txt |
WA |
532 ms |
512 KB |
1_17.txt |
AC |
605 ms |
512 KB |