• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 2021.7.21 义乌模拟赛 T4 D

6小时前 2次浏览

code:

``````#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db long double
#define N 100000
#define M 20000
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define it iterator
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,m,k,x,y,z,now,g[N+5];ll Sum[N+5],dp[N+5],l,r,mid,A[N+5];
I int check(ll mid){
re int i,j;now=0;for(i=1;i<=n;i++){
dp[i]=dp[i-1];g[i]=g[i-1];(dp[now]-Sum[now+1]<dp[i-1]-Sum[i]||(dp[now]-Sum[now+1]==dp[i-1]-Sum[i]&&g[i-1]>g[now]))&&(now=i-1);
if(dp[now]+Sum[i]-Sum[now+1]+mid>dp[i]||(dp[now]+Sum[i]-Sum[now+1]+mid==dp[i]&&g[now]+1>g[i]))dp[i]=dp[now]+Sum[i]-Sum[now+1]+mid,g[i]=g[now]+1;
}return g[n]>=k;
}
struct Solve2{
int las,L[N+5],R[N+5],op,Ansl[N+5],Ansr[N+5],now1,now2,cnt;
I void calc(int mid){
re int i;for(i=1;i<=n;i++){
dp[i]=dp[i-1];L[i]=L[i-1];R[i]=R[i-1];
(dp[now1]-Sum[now1+1]<dp[i-1]-Sum[i]||(dp[now1]-Sum[now1+1]==dp[i-1]-Sum[i]&&L[i-1]<L[now1]))&&(now1=i-1);
(dp[now2]-Sum[now2+1]<dp[i-1]-Sum[i]||(dp[now2]-Sum[now2+1]==dp[i-1]-Sum[i]&&R[i-1]>R[now2]))&&(now2=i-1);
(dp[now1]+Sum[i]-Sum[now1+1]+mid>dp[i]||(dp[now1]+Sum[i]-Sum[now1+1]+mid==dp[i]&&L[now1]+1<L[i]))&&(L[i]=L[now1]+1);
(dp[now2]+Sum[i]-Sum[now2+1]+mid>dp[i]||(dp[now2]+Sum[i]-Sum[now2+1]+mid==dp[i]&&R[now2]+1>R[i]))&&(R[i]=R[now2]+1);
dp[i]=max(dp[now1]+Sum[i]-Sum[now1+1]+mid,dp[i]);
}
for(i=n;i;i--){
if(!op){
if(L[i]<=k&&R[i]>=k&&((dp[i]==dp[Ansl[cnt]-1]||!cnt)&&(dp[i]^dp[i-1]||L[i-1]>k||R[i-1]<k)))Ansr[++cnt]=i,op=1;
}if(op){
if(L[i-1]<=k-1&&R[i-1]>=k-1&&(dp[i-1]+Sum[Ansr[cnt]]-Sum[i]+mid==dp[Ansr[cnt]])) Ansl[cnt]=i,op=0,k--;
}
}for(i=1;i<=cnt;i++) printf("%d %dn",Ansl[i],Ansr[i]);
}
}S;
int main(){
freopen("d.in","r",stdin);freopen("d.out","w",stdout);
re int i;scanf("%d%d",&n,&k);for(i=2;i<=n;i++) scanf("%lld",&A[i]),Sum[i]=Sum[i-1]+A[i];
l=-1e10+7;r=1e10+7;while(l+1<r) mid=l+r>>1,(check(mid)?r:l)=mid;check(r);printf("%lldn",dp[n]-r*k);S.calc(r);
}
``````