QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #829481 | #8936. Team Arrangement | 2021cyq# | ML | 0ms | 1540kb | C++14 | 891b | 2024-12-24 10:22:54 | 2024-12-24 10:22:55 |
Judging History
answer
#include<cstdio>
using namespace std;
int n,l[100],r[100],w[100],bj[100],i,j,t,ans;
void dfs(int c,int lim,int s)
{
int i,j,cnt,ll;
if(c==n)
{
if(s>ans)
ans=s;
return;
}
for(i=1;i<=n;i++)
if(bj[i]==0)
break;
ll=l[i];
for(i=lim;i>=ll;i--)
if(c+i<=n)
{
cnt=0;
for(j=1;j<=n&&cnt<i;j++)
if(bj[j]==0&&r[j]>=i)
{
cnt++;
bj[j]=c+114514;
}
if(cnt==i)
dfs(c+i,i,s+w[i]);
for(j=1;j<=n&&cnt>0;j++)
if(bj[j]==c+114514&&r[j]>=j)
{
cnt--;
bj[j]=0;
}
}
}
main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&l[i],&r[i]);
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(l[i]<l[j])
{
t=l[i];
l[i]=l[j];
l[j]=t;
t=r[i];
r[i]=r[j];
r[j]=t;
}
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
ans=-998244353;
dfs(0,n,0);
if(ans==-998244353)
printf("impossible");
else
printf("%d",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1464kb
input:
3 2 3 1 2 2 2 4 5 100
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 0ms
memory: 1480kb
input:
3 1 3 3 3 2 3 1 1 100
output:
100
result:
ok single line: '100'
Test #3:
score: 0
Accepted
time: 0ms
memory: 1460kb
input:
2 1 1 2 2 1 1
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 0ms
memory: 1540kb
input:
3 2 3 1 2 2 2 -100 -200 100000
output:
-300
result:
ok single line: '-300'
Test #5:
score: -100
Memory Limit Exceeded
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