QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#567556#9315. Rainbow Bracket SequenceATM12345WA 1ms10056kbC++141.1kb2024-09-16 12:46:322024-09-16 12:46:33

Judging History

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

  • [2024-09-16 12:46:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10056kb
  • [2024-09-16 12:46:32]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define LL long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define N 205
#define pb push_back
#define ld long double
#define all(x) x.begin(),x.end()
#define inf 1e18

using namespace std;
ll n,m;
ll a[Ma],c[Ma],v[Ma];
ll dp[N][N];


void clc()
{
	for (ll i=0;i<=n;i++)
		for (ll j=0;j<=n;j++)
			dp[i][j]=-inf;
	dp[0][0]=0;
}

void sol()
{
	cin>>n>>m;
	n<<=1;
	clc();
	for (ll i=1;i<=m;i++)
		cin>>a[i];
	
	for (ll i=1;i<=n;i++)
		cin>>c[i];
	for (ll i=1;i<=n;i++)
		cin>>v[i];
	for (ll i=1;i<=n;i++)
		for (ll j=(i+1)/2;j<=min(n,i);j++)
		{
			if (a[c[i]]<=i)
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+v[i]);
			else
				dp[i][j]=dp[i-1][j];
			//printf("i=%lld j=%lld dp=%lld\n",i,j,dp[i][j]);
		}
	ll ans=dp[n][n/2];
	if (ans<0)
		printf("-1\n");
	else
		printf("%lld\n",ans);
	return;
}

int main()
{
	IOS
	ll tt=1;
	cin>>tt;
	while (tt--)
		sol();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7936kb

input:

2
3 2
1 2
1 2 2 2 1 2
3 1 4 2 2 1
3 2
2 2
1 2 2 2 1 2
3 1 4 2 2 1

output:

9
-1

result:

ok 2 number(s): "9 -1"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 10056kb

input:

50
8 6
0 2 2 0 3 1
3 5 1 1 5 3 5 2 3 2 2 1 2 2 4 6
998133227 879226371 59632864 356493387 62611196 827258251 296576565 204244054 812713672 780267148 614679390 447700005 102067050 544546349 116002772 761999375
1 1
1
1 1
343766215 374461155
3 1
2
1 1 1 1 1 1
796323508 303640854 701432076 853325162 610...

output:

-1
343766215
-1
3426965219
-1
-1
1351561190
-1
-1
5372255482
1311169903
-1
-1
2719131728
3983627641
-1
3121174891
1046749330
-1
4997298213
3914858167
-1
4270179075
2566553992
-1
5977120748
7505501534
5477900047
-1
1467678317
883992368
1232523916
7252236339
-1
3950279808
1447294256
-1
3889754605
-1
-...

result:

wrong answer 3rd numbers differ - expected: '2351080746', found: '-1'