BZOJ5311 贞鱼（动态规划+wqs二分+决策单调性）

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 4010
char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
    int x=0;char c=getchar();
    while (c<‘0‘||c>‘9‘) c=getchar();
    while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}
struct FastIO {
    static const int S = 1e7;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) exit(0);
        return buf[pos++];
    }
    inline int xuint() {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; ‘0‘ <= c && c <= ‘9‘; c = xchar()) x = x * 10 + c - ‘0‘;
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == ‘-‘) s = -1, c = xchar();
        for (; ‘0‘ <= c && c <= ‘9‘; c = xchar()) x = x * 10 + c - ‘0‘;
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos++] = x;
    }
    inline void wint(ll x)
    {
        if (x < 0) wchar(‘-‘), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n++] = ‘0‘ + x % 10, x /= 10;
        while (n--) wchar(s[n]);
        wchar(‘\n‘);
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
int n,m,a[N][N],g[N],stk[N],L[N],R[N],top;
ll f[N];
int calc(int i,int j){return a[j][j]-a[i-1][j]-a[j][i-1]+a[i-1][i-1]>>1;}
bool isbetter(int x,int y,int i){return f[x]+calc(x+1,i)<f[y]+calc(y+1,i)||f[x]+calc(x+1,i)==f[y]+calc(y+1,i)&&g[x]<g[y];}
pair<int,ll> check(int cost)
{
    memset(f,42,sizeof(f));f[0]=0;
    stk[top=1]=0,L[1]=1,R[1]=n;
    for (int i=1;i<=n;i++)
    {
        int l=1,r=top,x;
        while (l<=r) 
        {
            int mid=l+r>>1;
            if (R[mid]>=i) x=stk[mid],r=mid-1;
            else l=mid+1;
        }
        f[i]=f[x]+calc(x+1,i)+cost;
        g[i]=g[x]+1;
        while (L[top]>i&&isbetter(i,stk[top],L[top])) top--;
        l=i+1,r=R[top],x=R[top]+1;
        while (l<=r)
        {
            int mid=l+r>>1;
            if (isbetter(i,stk[top],mid)) x=mid,r=mid-1;
            else l=mid+1;
        }
        R[top]=x-1;if (x<=n) stk[++top]=i,L[top]=x,R[top]=n;
    }
    return make_pair(g[n],f[n]);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj5311.in","r",stdin);
    freopen("bzoj5311.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++)
        for (int j=1;j<=n;j++)
        a[i][j]=a[i-1][j]+a[i][j-1]+io.xint()-a[i-1][j-1];
    int l=-100000000,r=-l,ans;
    while (l<=r)
    {
        int mid=l+r>>1;
        if (check(mid).first<=m) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<check(ans).second-1ll*m*ans;
    return 0;
}