CF321E

#include<bits/stdc++.h>
using namespace std;
const int N=4e3+5;
int n,m,a[N][N],dp[805][N],pos[805][N];
int w(int l,int r){
    return a[r][r]-a[r][l-1]-a[l-1][r]+a[l-1][l-1];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j],a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        dp[1][i]=w(1,i),pos[1][i]=i;
    }
    for(int k=2;k<=m;k++){
        pos[k][n+1]=n;
        for(int i=n;i>=1;i--){
            dp[k][i]=2e9;
            for(int j=max(2,pos[k-1][i]);j<=pos[k][i+1];j++){
                if(dp[k-1][j-1]+w(j,i)<dp[k][i]){
                    dp[k][i]=dp[k-1][j-1]+w(j,i),pos[k][i]=j;
                }
            }
        }
    }
    cout<<dp[m][n]/2;
}