A：搜索好难啊根本不会啊。
B：暴力枚举给哪段前缀乘，维护一些前后缀最大最小值之类的东西就很好算了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 1000010
#define ll long long
int n,w,v,a[N];
ll ans=-,sum[N],pre[N],suf[N];
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=read(),w=-read(),v=-read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=n;i++) sum[i]=sum[i-]+a[i];
for (int i=;i<=n+;i++) pre[i-]=suf[i]=(sum[n]-sum[i-])*v+sum[i-];
for (int i=;i<=n;i++) pre[i]=max(pre[i],pre[i-]);
for (int i=n;i;i--) suf[i]=min(suf[i],suf[i+]);
for (int i=;i<=n;i++)
ans=max(ans,min(sum[i]*w+suf[i+]-sum[i],(sum[n]-sum[i])*v+(pre[i]-(sum[n]-sum[i])*v)*w));
cout<<ans;
return ;
}
C：吐槽一下这场的心路历程。开场看A，看了一会性质发现转化成了一个2-SAT，这玩意怎么还能计数啊？盯了一个小时一点都不会，暴力都没写就跑了。心态从这就开始崩了。然后半个小时搞掉B。C开始胡乱分析一下觉得某结论很显然，然后写了一个小时差不多搞定了，结果因为各种写挂，大样例跑的比答案大。然而并没有冷静下来去验证结论，并且由于数据范围才50觉得自己肯定假掉了，于是开始退火。退了半天总是比答案小，到处找锅没有任何收获，最后弃疗了连交都没交了。之后调了两个小时才发现做mst时边权开的是int于是炸成负数了。
这个题胡乱分析一下性质跑mst就好了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 55
#define T1 1e5
#define T2 1e-8
#define delta 0.98
int n,a[N][N],b[N][N],id[N],id2[N],dfn[N],fa[N],c;
long long t[N],u[N],f[N],tmp[N],dis[N][N],ans,tot=;
bool cmp(const int&a,const int&b)
{
return f[a]>f[b];
}
struct data
{
int x,y;long long z;
bool operator <(const data&a) const
{
return z<a.z;
}
}edge[N*N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void SWAP(int x,int y)
{
swap(id[x],id[y]);
dfn[id[x]]=x,dfn[id[y]]=y;
}
long long getans()
{
ans=;
for (int i=;i<=n;i++) fa[i]=i;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (a[i][j]) fa[find(i)]=find(j);
for (int i=;i<=n;i++)
{
for (int j=;j<=n;j++)
if (a[i][j])
if (dfn[j]<dfn[i]) ans+=u[j]*f[i]*(u[i]-t[i]);
else if (dfn[j]>dfn[i]) ans+=t[j]*f[i]*(u[i]-t[i]);
ans+=f[i]*((u[i]-)+t[i])*(u[i]-t[i])>>;
}
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
dis[i][j]=;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (dfn[i]<dfn[j])
{
int p=find(i),q=find(j);
if (p!=q) dis[p][q]=min(dis[p][q],(t[i]+t[j])*c+t[j]*f[i]*(u[i]-t[i])+u[i]*f[j]*(u[j]-t[j]));
}
int cnt=;memset(id2,,sizeof(id2));
for (int i=;i<=n;i++) if (find(i)==i) id2[++cnt]=i;
int num=;
for (int i=;i<=cnt;i++)
for (int j=;j<=cnt;j++)
num++,edge[num].x=id2[i],edge[num].y=id2[j],edge[num].z=dis[id2[i]][id2[j]];
sort(edge+,edge+num+);
for (int i=;i<=n;i++) fa[i]=i;
for (int i=;i<=num;i++)
if (find(edge[i].x)!=find(edge[i].y)) ans+=edge[i].z,fa[find(edge[i].x)]=edge[i].y;
return ans;
}
void solve()
{
double T=T1;
long long lastans=tot;
while (T>T2)
{
int x=rand()%(n-)+,y=rand()%(n-x)+x+;
SWAP(x,y);
ans=getans();
if (ans<lastans||exp((lastans-ans)/T)>1.0*rand()/RAND_MAX) tot=min(tot,ans);
else SWAP(x,y),ans=lastans;
T*=delta;lastans=ans;
}
}
int main()
{
freopen("reconstruction.in","r",stdin);
freopen("reconstruction.out","w",stdout);
n=read();srand(time());
for (int i=;i<=n;i++) t[i]=read();
for (int i=;i<=n;i++) u[i]=read();
for (int i=;i<=n;i++) f[i]=read();
if (n==) {cout<<(f[]*((u[]-)+t[])*(u[]-t[])>>);return ;}
for (int i=;i<=n;i++)
{
for (int j=;j<=n;j++)
{
char c=getchar();
while (c!='Y'&&c!='N') c=getchar();
if (c=='Y') a[i][j]=;
}
}
c=read();
for (int i=;i<=n;i++) id[i]=i;
sort(id+,id+n+,cmp);
for (int i=;i<=n;i++) dfn[id[i]]=i;
tot=getans();
//solve();
cout<<tot;
return ;
}
result：- rank-