显然可以dp。显然可以单调队列优化一下。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 100010int n,m,q[N];long long a[N],f[N];int main(){#ifndef ONLINE_JUDGE freopen("bzoj2442.in","r",stdin); freopen("bzoj2442.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=a[i-1]+read(); int head=1,tail=1; for (int i=1;i<=n+1;i++) { while (q[head]