QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#567543#9315. Rainbow Bracket SequenceATM12345WA 0ms7972kbC++141.2kb2024-09-16 12:38:472024-09-16 12:38:47

Judging History

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

  • [2024-09-16 12:38:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7972kb
  • [2024-09-16 12:38:47]
  • 提交

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 (j>m||c[i]>=a[j])
				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;
}

详细

Test #1:

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

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: 7972kb

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:

5519435604
343766215
-1
3426965219
2613951631
-1
1351561190
-1
-1
5372255482
1158637046
5938245406
2231197660
2719131728
3983627641
-1
-1
1046749330
-1
4997298213
3914858167
3902088946
4270179075
2566553992
5807725675
5977120748
7505501534
-1
5054275471
1467678317
883992368
1232523916
7252236339
-1
...

result:

wrong answer 1st numbers differ - expected: '-1', found: '5519435604'