結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+5;
ll a[MAXN],n,m,c;
struct edge{
	ll v,w;
};
vector<edge> G[MAXN];
ll dis[MAXN],vis[MAXN];
struct node{
	ll dis,u;
	bool operator>(const node& a) const {
		return dis>a.dis; 
	}
};
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
    }
    return x*f;
}
priority_queue<node,vector<node>,greater<node> >q;
void dijkstra(int s){
	for(int i=0;i<=n+1;++i){
		dis[i]=0x3f3f3f3f3f3f3f3f;
		vis[i]=0;
	}
	dis[s]=0;
	q.push({0,s});
	while (!q.empty()){
		ll u=q.top().u;
		q.pop();
		if (!vis[u]){
			vis[u]=1;
			for(auto Q:G[u]){
				ll v=Q.v,w=Q.w;
				if (dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					q.push({dis[v],v});
				}
			}
		}
	}
	
}
int main(){
	ll T=1;
	while (T--){
		ll sum=0;
		n=read(),m=read(),c=read();	
		for(int i=1;i<=n;++i){
			a[i]=read();
			G[i].push_back({i+1,a[i]});
			G[i+1].push_back({i,a[i]});
			sum+=a[i];
		}
		for(int i=1;i<=m;++i){
			ll l=read(),r=read();
			G[l].push_back({r+1,c});
			G[r+1].push_back({l,c});
		}
		dijkstra(1);
//		cout<<sum<<" "<<dis[n+1]<<endl;
		printf("%lld\n",sum-dis[n+1]);
		for(int i=1;i<=n+1;++i){
			G[i].clear();
		}
	}
	return 0;
}
0