P5322 [BJOI2019] 排兵布阵

点击查看代码

#include<bits/stdc++.h>
using namespace std;

const int N=105,M=2e4+10;
int f[M];
vector<int> a[N];
int s,n,m;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);

    cin>>s>>n>>m;

    for(int i=1;i<=s;i++){
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            a[j].push_back(x);
        }
    }

    for(int i=1;i<=n;i++){
        sort(a[i].begin(),a[i].end());
        for(int j=m;j>=0;j--){
            for(int k=0;k<s;k++){
                int cost=2*a[i][k]+1;
                if(cost>j) break;
                f[j]=max(f[j],f[j-cost]+(k+1)*i);
            }
        }
    }

    cout<<f[m]<<endl;

    return 0;
}