题目链接

CF1219G Harvester

解题思路

就是个嗯分讨题。

发现最终选择的方案总共就以下五种情况：

• 选 \(4\) 行 \(0\) 列。

• 选 \(3\) 行 \(1\) 列。

• 选 \(2\) 行 \(2\) 列。

• 选 \(1\) 行 \(3\) 列。

• 选 \(0\) 行 \(4\) 列。

对于第一，五种情况，直接取每行或每列的前四大值即可，时间复杂度 \(O(n \log n)\)。

对于第二，四种情况，直接枚举取的单独的一行或一列。然后取每行或每列的前三大值即可，注意要去重，时间复杂度 \(O(nm \log n)\)。

对于第三种情况，我们可以直接枚举取的那两行。然后取每列的前二大值即可，注意要去重，时间复杂度 \(O(n^2m)\)。

总时间复杂度 \(O(n^2m)\)，如果有 \(n > m\),记得翻转矩阵，这样就会有 \(n \le \sqrt{10^5}\)，可以通过此题。

参考代码

#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re int (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}
template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}
ll _t_;
void _clear(){}
ll n,m;
bool cmp(ll x,ll y){
    return x>y;
}
void solve()
{
    _clear();
    cin>>n>>m;
    ll c[n+5][m+5];
    ll a[min(n,m)+5][max(n,m)+5],b[m+5][n+5];
    ll ans=-1e18;
    forl(i,1,n)
        forl(j,1,m)
            cin>>c[i][j];
    if(n>m)
    {
        forl(i,1,n)
            forl(j,1,m)
                b[j][i]=c[i][j];
        swap(n,m);
        forl(i,1,n)
            forl(j,1,m)
                a[i][j]=b[i][j];
    }
    else
    {
        forl(i,1,n)
            forl(j,1,m)
                a[i][j]=c[i][j];
    }
    ll sumx[n+5]={},sumy[m+5]={},d[max(n,m)*2+5]={},k=0;
    forl(i,1,n)
        forl(j,1,m)
            sumx[i]+=a[i][j];
    forl(i,1,n)
        forl(j,1,m)
            sumy[j]+=a[i][j];
    k=0;
    forl(i,1,n)
        d[++k]=sumx[i];
    sort(d+1,d+1+k,cmp);
    Max(ans,d[1]+d[2]+d[3]+d[4]);
    forl(i,0,max(n,m)+4)
        d[i]=0;
    k=0;
    forl(i,1,m)
        d[++k]=sumy[i];
    sort(d+1,d+1+k,cmp);
    Max(ans,d[1]+d[2]+d[3]+d[4]);
    forl(i,0,max(n,m)+4)
        d[i]=0;

    forl(i,1,n)
    {
        forl(j,0,k+4)
            d[j]=0;
        k=0;
        forl(j,1,m)
            d[++k]=sumy[j]-a[i][j];
        sort(d+1,d+1+k,cmp);
        Max(ans,sumx[i]+d[1]+d[2]+d[3]); 
    }
    k=0;
    forl(i,0,max(n,m)+4)
        d[i]=0;

    forl(i,1,m)
    {
        forl(j,0,k+4)
            d[j]=0;
        k=0;
        forl(j,1,n)
            d[++k]=sumx[j]-a[j][i];
        sort(d+1,d+1+k,cmp);
        Max(ans,sumy[i]+d[1]+d[2]+d[3]); 
    }
    k=0;
    forl(i,0,max(n,m)+4)
        d[i]=0;   

    forl(i,1,n)
        forl(j,i+1,n)
        {
            ll maxn1=0,maxn2=0;
            forl(l,0,k+4)
                d[l]=0;
            k=0;
            forl(l,1,m)
            {
                ll num=sumy[l]-a[i][l]-a[j][l];
                if(maxn1==0)
                    maxn1=num;
                else if(maxn2==0)
                {
                    maxn2=num;
                    if(maxn1<maxn2)
                        swap(maxn1,maxn2);
                }
                else
                {
                    if(num>=maxn1)
                        maxn2=maxn1,maxn1=num;
                    else if(num>=maxn2)
                        maxn2=num;
                }
            }
            Max(ans,sumx[i]+sumx[j]+maxn1+maxn2);
        }
    cout<<ans<<endl;
}
int main()
{
//    freopen("tst.txt","r",stdin);
//    freopen("sans.txt","w",stdout);
    IOS;
    _t_=1;
//    cin>>_t_;
    while(_t_--)
        solve();
    QwQ;
}