代码1：

#include<bits/stdc++.h>
using namespace std;
long long n,m,p,d[1<<17],t[1<<17],a[1<<17],s[1<<17],f[128][1<<17],H,T,i=1,j,h,q[1<<17];
auto g(int k,int j){return f[j-1][k]+s[k];}
main(){
    for(cin>>n>>m>>p;i++<n;d[i]+=d[i-1])cin>>d[i];
    for(i=0;i++<m;a[i]=t[i]-d[h])cin>>h>>t[i];
    for(sort(a+1,a+m+1),i=0;i++<m;s[i]=s[i-1]+a[i]);
    for(memset(f,63,1<<27),i=0;i<=p;)f[i++][0]=0;
    for(j=0;j++<p;)for(T=q[H=0]=i=0;i++<m;q[++T]=i){
        for(;H<T&&(g(q[H+1],j)-g(q[H],j))<=a[i]*(q[H+1]-q[H]);H++);
        for(f[j][i]=f[j-1][q[H]]-a[i]*q[H]+s[q[H]]+a[i]*i-s[i];H<T&&(g(q[T],j)-g(q[T-1],j))*(i-q[T])>=(g(i,j)-g(q[T],j))*(q[T]-q[T-1]);T--);
    }
    cout<<f[p][m];
}

代码2：

#include<bits/stdc++.h>
using namespace std;
int n,mx=-1e9,a[222],g[222][222],i,s,k,r;
main(){
    for(cin>>n;i++<n;a[i+n]=a[i])cin>>a[i];
    for(s=2;s++<=n;)for(i=0;s+i++<=n*2;)for(r=(k=i)+s-1;k++<r-1;)g[i][r]=max(g[i][r],g[i][k]+g[k][r]+a[i]*a[k]*a[r]);
    for(i=0;i++<n;mx=max(g[i][i+n],mx));
    cout<<mx;
}

代码3：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,S,a[1<<15],d[1<<15],V[1<<15],u,v,w;
vector<array<int,2>>g[1<<15];
main(){
    for(cin>>n>>m>>S>>S;m--&&cin>>u>>v>>w;)g[u].push_back({v,w}),g[v].push_back({u,w});
    for(;cin>>u>>v>>w;)g[u].push_back({v,w});
    deque<int>q; 
    for(q.push_back(S),memset(d,0x3f,sizeof d),d[S]=0,V[S]=1;q.size();){
        int v=q.front();
        q.pop_front(),V[v]=0;
        for(auto[u,w]:g[v])if(d[u]>d[v]+w){
            d[u]=d[v]+w;
            if(!V[u])V[u]=1,(q.size()&&d[u]<d[q.front()])?q.push_front(u):q.push_back(u);
        }
    }
    for(int i=1;i<=n;i++)d[i]>5e8?cout<<"NO PATH\n":cout<<d[i]<<endl;
}

代码写成这样我还有救吗