QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100323#5378. 匹配问题zhouhuanyi0 2ms3604kbC++231.3kb2023-04-25 16:38:492023-04-25 16:38:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 16:38:52]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3604kb
  • [2023-04-25 16:38:49]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 5000
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
void Adder(int &x,int d)
{
    x=(x<d)?d:x;
    return;
}
int n,ans,la,lb,a[N+1],b[N+1],l[N+1],r1[N+1],r2[N+1],st[N+1],dp[N+1][N+1];
int get_maxn(int sl,int sr)
{
    int maxn=-inf;
    for (int i=sl;i<=sr;++i) maxn=max(maxn,l[i]-i+1);
    return maxn;
}
int main()
{
    n=read(),la=read(),lb=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i) b[i]=read();
    sort(a+1,a+n+1),sort(b+1,b+n+1);
    for (int i=1;i<=n;++i) l[i]=lower_bound(b+1,b+n+1,a[i])-b-1,r1[i]=lower_bound(b+1,b+n+1,a[i]+la+1)-b-1,r2[i]=lower_bound(b+1,b+n+1,a[i]+lb+1)-b-1;
    for (int i=1;i<=n;++i) st[i]=l[i]-i+1;
    for (int i=2;i<=n;++i) st[i]=max(st[i],st[i-1]);
    for (int i=0;i<=n;++i)
	for (int j=0;j<=i;++j)
	    dp[i][j]=-inf;
    dp[0][0]=0;
    for (int i=1;i<=n;++i)
	for (int j=i-1;j>=0;--j)
	{
	    //A
	    Adder(dp[i][i],dp[i-1][j]);
	    //B
	    if (max(r1[j],r2[i])>=st[j]+i&&r2[i]>=get_maxn(j+1,i)+i) Adder(dp[i][j],dp[i-1][j]+1);
	}
    for (int i=0;i<=n;++i) Adder(ans,dp[n][i]);
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 2ms
memory: 3500kb

input:

2 2 1
1 1
1 1

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

10 200000 100000
34181 300096 24293 22680 402306 193269 438170 254676 188147 73971
216849 477743 461911 135785 467234 278230 287107 223666 124173 135091

output:

7

result:

ok single line: '7'

Test #3:

score: -4
Wrong Answer
time: 2ms
memory: 3604kb

input:

10 200000 50000
298370 136488 436143 52173 206095 140981 321188 407844 342157 193338
138374 383207 156748 442404 386749 492604 354156 229996 447123 418264

output:

7

result:

wrong answer 1st lines differ - expected: '5', found: '7'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #100:

score: 0
Runtime Error

input:

500000 500000 10
200184 74991 71203 334998 316800 34483 120570 301054 331108 232072 189788 397143 490296 56807 361700 88818 42376 460305 371750 450351 338384 429789 426045 445029 152316 408919 188124 144966 457495 475025 225370 260510 383159 495247 54319 246245 240728 372033 439599 119720 449020 451...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%