QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762164#8528. ChordsGrain_Depot08WA 1ms6392kbC++14699b2024-11-19 14:00:512024-11-19 14:00:55

Judging History

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

  • [2024-11-19 14:00:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6392kb
  • [2024-11-19 14:00:51]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define N 100005

int n,l[N];

vector<int>f[N];

int main(){
	int u,v;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		l[v]=u;
	}
	f[0].push_back(0);
	for(int i=1,j;i<=n+n;++i){
		f[i]=f[i-1];
		f[i][0]=i;
		if(!l[i])continue;
		for(j=f[i].size()-1;~j;--j){
			if(f[i-1][j]>l[i]){
				break;
			}
		}
		if(f[i].size()==j+1){
			f[i].push_back(l[i]);
		}else{
			f[i][j+1]=l[i];
		}
		for(int k=1;k<f[l[i]-1].size();++k){
			if(k+j+1==f[i].size()){
				f[i].push_back(f[l[i]-1][k]);
			}else{
				f[i][k+j+1]=max(f[i][k+j+1],f[l[i]-1][k]);
			}
		}
	}
	printf("%d",f[n+n].size());
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2
4 10
7 9
3 5
6 8

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 6388kb

input:

2
1 3
2 4

output:

2

result:

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