QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302096#7988. 史莱姆工厂PhantomThreshold#TL 0ms3828kbC++201.3kb2024-01-10 16:13:232024-01-10 16:13:24

Judging History

你现在查看的是最新测评结果

  • [2024-01-10 16:13:24]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3828kb
  • [2024-01-10 16:13:23]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 200;
const int maxk = 12;
const ll inf  = 1e15;

int n,K,W;
int ci[maxn],mi[maxn];
int pi[maxn];


signed main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n>>K>>W;
	for(int i=1;i<=n;i++) cin>>ci[i];
	for(int i=1;i<=n;i++) cin>>mi[i];
	for(int i=K;i<=2*K-2;i++) cin>>pi[i];
	auto elim=[&](vector<pair<int,int>>& now)
	{
		int ok=0,sum=0;
		while(not ok)
		{
			ok=1;
			for(int i=0;i<(int)now.size();i++)
			{
				if(now[i].second>=K)
				{
					sum+=pi[now[i].second];
					now.erase(now.begin()+i);
					ok=0;
					break;
				}
				if(i+1<(int)now.size() and now[i].first==now[i+1].first)
				{
					now[i].second+=now[i+1].second;
					now.erase(now.begin()+i+1);
					ok=0;
					break;
				}
			}
		}
		return sum;
	};
	long long ans=-inf;
	function<void(vector<pair<int,int>>,int)> dfs=[&](vector<pair<int,int>> now,int cost)
	{
		if(now.empty())
		{
			ans=max(ans,cost);
			return;
		}
		for(int i=0;i<(int)now.size();i++)
		{
			auto tmp=now;
			int tw=K-tmp[i].second;
			tmp[i].second=K;
			int del=elim(tmp);
			dfs(tmp,cost+del-tw*W);
		}
	};
	vector<pair<int,int>> a;
	for(int i=1;i<=n;i++)a.emplace_back(ci[i],mi[i]);
	dfs(a,0);
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3828kb

input:

4 5 6
2 1 2 3
3 3 3 4
5 7 9 11

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

5 7 500
2 3 2 3 2
5 6 6 6 4
1000 900 800 400 200 50

output:

1400

result:

ok single line: '1400'

Test #3:

score: -100
Time Limit Exceeded

input:

150 10 465782
6 1 4 3 2 6 1 3 5 3 4 6 1 2 1 5 1 6 2 1 5 4 6 1 3 2 6 5 4 3 1 6 3 4 1 4 1 6 3 6 1 4 2 4 6 4 3 1 5 6 4 2 1 4 6 2 5 1 3 1 4 6 5 6 3 2 3 4 2 3 6 3 5 2 6 1 5 4 5 2 4 1 4 3 4 1 3 2 6 1 4 5 4 6 2 1 3 1 2 1 3 5 2 3 2 6 5 3 1 4 1 5 1 6 2 5 4 2 4 1 4 2 5 6 4 3 5 1 3 2 5 4 6 4 3 5 3 4 5 3 2 1 4 ...

output:


result: