CSP前的挣扎：

这是一道背包问题

#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=105,M=2e4+5;
int n,s,m,a[N][N],f[M];
il int read()
{
   int x,f=1;char ch;
   _(!)ch=='-'?f=-1:f;x=ch^48;
   _()x=(x<<1)+(x<<3)+(ch^48);
   return f*x;
}
int main()
{
    s=read();n=read();m=read();
    for(int i=1;i<=s;i++)for(int j=1;j<=n;j++)a[j][i]=read()*2+1;
    for(int i=1;i<=n;i++)sort(a[i]+1,a[i]+1+s);
    for(int i=1;i<=n;i++)for(int j=m-1;j>=0;j--)
    {
        for(int k=1;k<=s;k++)
        {
            if(a[i][k]+j>m)break;
            f[a[i][k]+j]=max(f[a[i][k]+j],f[j]+k*i);
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

祝各位CSP选手

RP++\color{red}{RP++}

注释：

fi,jf_{i,j} 表示选到前 ii 座城堡已经用了 jj 个士兵所能获得总分的最大值。

倘若直接枚举每座城堡派几个士兵效率是 O(nm2)O(nm^{2}) ，但是我们发现只有多获胜一个人才能使总分增多，所以我们可以考虑枚举每座城堡赢几个人，效率变成 O(nms)O(nms) 。