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
AC × 3
AC × 17
WA × 4
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