2020多校第二場1010
14841 ワード
構想
推定複雑度はk^(n/k)であり,この関数はk=3,n=50で最大である.このときの演算量は大きくなく,dfs暴力が可能である.あるタイプのアイテムが空の場合に注意するには、処理を最適化する必要があります.
コード#コード#
推定複雑度はk^(n/k)であり,この関数はk=3,n=50で最大である.このときの演算量は大きくなく,dfs暴力が可能である.あるタイプのアイテムが空の場合に注意するには、処理を最適化する必要があります.
コード#コード#
#include
#define hi cout<
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
using namespace std;
const ll mod = 1000000009;
const int N = 1e7+1;
ll power(long long a, long long b, long long mode)
{
long long sum = 1;
while (b) {
if (b & 1) {
sum = (sum * a) % mode;
b--;
}
b /= 2;
a = a * a % mode;
}
return sum;
}
ll gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
ll lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
struct st
{
ll a,b,c,d;
};
vector<st> v[55];
ll ans=0,cot=0;
ll k;
map<ll,ll> m;
ll dfs(ll type,ll a,ll b,ll c,ll d)
{
if(type==cot+1)
{
return (a)*(b)*(c)*(d);
}
for(int i=0;i<v[type].size();i++)
{
st tmp=v[type][i];
ans=max(ans,dfs(type+1,a+tmp.a,b+tmp.b,c+tmp.c,d+tmp.d));
}
return ans;
}
int main()
{
int T;
cin>>T;
while(T--)
{
ans=0;
cot=0;
int n;
scanf("%d%lld",&n,&k);
for(int i=0;i<=k+2;i++)
{
v[i].clear();
}
m.clear();
for(int i=0;i<n;i++)
{
st tmp;
int t;
scanf("%d%lld%lld%lld%lld",&t,&tmp.a,&tmp.b,&tmp.c,&tmp.d);
if(!m[t])
{
m[t]=++cot;
}
v[m[t]].push_back(tmp);
}
printf("%lld
",dfs(1,100,100,100,100));
}
}