結果
問題 |
No.2321 Continuous Flip
|
ユーザー |
![]() |
提出日時 | 2025-08-26 15:42:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 292 ms / 2,000 ms |
コード長 | 1,045 bytes |
コンパイル時間 | 3,144 ms |
コンパイル使用メモリ | 286,836 KB |
実行使用メモリ | 30,604 KB |
最終ジャッジ日時 | 2025-08-26 15:42:28 |
合計ジャッジ時間 | 12,882 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; const long long INF = 1e18; int n, m, w, vis[N]; long long dis[N]; vector<pair<int, int>> e[N]; int main() { ios :: sync_with_stdio(false), cin.tie(0); cin >> n >> m >> w; long long sumA = 0; for (int i = 1; i <= n; i++) { int a; cin >> a; sumA += a; e[i].emplace_back(i + 1, a); e[i + 1].emplace_back(i, a); } for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; e[l].emplace_back(r + 1, w); e[r + 1].emplace_back(l, w); } fill(dis + 1, dis + 2 + n, INF); priority_queue<pair<long long, int>> q; q.push({dis[1] = 0, 1}); while (!q.empty()) { int x = q.top().second; q.pop(); if (vis[x]) { continue; } vis[x] = 1; for (auto i : e[x]) { int y = i.first; long long v = dis[x] + i.second; if (v < dis[y]) { q.push({-(dis[y] = v), y}); } } } cout << sumA - dis[n + 1] << "\n"; return 0; }