QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#630998	#8936. Team Arrangement	FHQY^#	TL	0ms	3968kb	C++20	1.0kb	2024-10-11 21:18:34	2024-10-11 21:18:34

Judging History

This is the latest submission verdict.

[2024-10-11 21:18:34]
Judged

Verdict: TL
Time: 0ms
Memory: 3968kb

Show

[2024-10-11 21:18:34]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=61;
struct seg{int l,r;}a[N];
int b[N],w[N],m,n;
int ans=-2e9;
bool cmp(seg a,seg b){
	if(a.r!=b.r)return a.r<b.r;
	else return a.l<b.l;
}
bool check(){
	multiset<int>s;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=b[i];j++)s.insert(b[i]);
	for(int i=1;i<=n;i++){
		auto now=s.lower_bound(a[i].l);
		if(now==s.end())return 0;
		if((*now)>a[i].r)return 0;
		s.erase(now);
	}
	return 1;
}
void out(){
	printf("the number : %d\n",m);
	for(int i=1;i<=m;i++)
		printf("%d ",b[i]);
	puts("");
}
void dfs(int las,int rm){
	if(rm==0){
//		out();
		int tmp=0;
		for(int i=1;i<=m;i++)
			tmp+=w[b[i]];
		if(tmp<=ans)return;
		if(check())ans=tmp;
		return;
	}
	for(int i=las;i>=1;i--)
		if(rm-i>=0){
			b[++m]=i;
			dfs(i,rm-i);
			--m;
		}
}
int main(){
	scanf("%d",&n);	
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].l,&a[i].r);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	sort(a+1,a+n+1,cmp);
	dfs(n,n);
	if(ans==-2e9)puts("impossible");
	else cout<<ans<<endl;
	return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3956kb

input:

output:

result:

ok single line: '9'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3968kb

input:

output:

result:

ok single line: '100'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3636kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

3
2 3
1 2
2 2
-100 -200 100000

output:

-300

result:

ok single line: '-300'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

9
1 4
2 5
3 4
1 5
1 1
2 5
3 5
1 3
1 1
1 1 1 1 1 1 1 1 1

output:

result:

ok single line: '6'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3924kb

input:

14
3 3
1 2
2 3
2 3
2 3
1 1
2 3
1 3
3 3
1 3
1 3
1 2
2 3
1 3
-9807452 -9610069 4156341 2862447 6969109 -7245265 -2653530 -5655094 6467527 -6872459 3971784 7312155 9766298 -2719573

output:

-16558567

result:

ok single line: '-16558567'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

14
1 2
1 4
2 3
3 5
4 5
2 5
2 4
2 4
1 2
3 4
1 5
2 4
1 1
4 5
-13763 -7354207 1096407 -9063321 -4824546 -6275546 1258145 -5272834 -8631107 3581157 2320771 -7714508 8446625 -6816167

output:

-2673021

result:

ok single line: '-2673021'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

14
2 3
4 4
1 7
3 6
3 4
1 1
1 4
4 7
3 7
1 7
2 3
6 6
1 1
3 6
2923142 1686477 640352 2848353 9202543 -4441381 4866381 -3610520 8124124 -1372894 1111310 -7538627 466143 9937961

output:

result:

ok single line: '5939733'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

14
1 7
1 2
8 8
1 1
7 8
6 9
7 8
1 4
6 9
3 3
1 1
3 7
5 8
4 8
-7139089 6365816 -9893288 5936146 -2803918 -4961415 1495365 -2564851 -2630365 -8608883 5813455 -4005459 -8844054 6703783

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

14
6 13
3 7
2 13
6 8
4 5
12 13
3 10
4 11
2 14
3 4
5 13
10 14
10 14
3 12
-8599727 -1496394 855072 -7439122 -5170228 8009298 -250221 5841035 2949765 7166358 -3516548 -6851737 8173765 -917122

output:

impossible

result:

ok single line: 'impossible'

Test #11:

score: -100

Time Limit Exceeded

input: