結果

問題 No.2321 Continuous Flip
コンテスト
ユーザー vjudge1
提出日時 2025-08-27 12:27:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 299 ms / 2,000 ms
コード長 1,302 bytes
コンパイル時間 2,111 ms
コンパイル使用メモリ 203,200 KB
実行使用メモリ 31,636 KB
最終ジャッジ日時 2025-08-27 12:27:40
合計ジャッジ時間 10,465 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int c, T, n, a[N], m;
long long dis[N];
int vis[N];
vector<pair<int, int> > G[N];
using pii = pair<long long, int>;
priority_queue<pii, vector<pii>, greater<pii >  > Q;
long long dijkstra() {
    for (int i = 0; i <= n; i++) dis[i] = 1e18, vis[i] = 0;
    dis[0] = 0;
    Q.push({0ll, 0});
    while (!Q.empty()) {
        int u = Q.top().second; Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto it : G[u]) {
            int v = it.first, w = it.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({dis[v], v});
            }
        }
    }
    return dis[n];
}
void solve() {
    cin >> n >> m >> c;
    for (int i = 0; i <= n; i++) G[i].clear();
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        G[i - 1].push_back({i, a[i]});
        G[i].push_back({i - 1, a[i]});
    }
    
    for (int i = 1, l, r; i <= m; i++) {
        cin >> l >> r;
        G[l - 1].push_back({r, c});
        G[r].push_back({l - 1, c});
    }
    cout << sum - dijkstra() << '\n';
}
int main() {

    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    T = 1;
    while (T--) solve();
    return 0;
}
0