QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#826383 | #8936. Team Arrangement | hotdogseller | TL | 0ms | 3844kb | C++14 | 1.4kb | 2024-12-22 09:42:25 | 2024-12-22 09:42:25 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define maxn 65
#define double long double
#define INF 1e18
#define mod 998244353
using namespace std;
inline int read(){
int lre=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(isdigit(c)){
lre=(lre<<3)+(lre<<1)+(c-'0');
c=getchar();
}
return lre*f;
}
int n,res=-INF;
int l[maxn],r[maxn];
int w[maxn];
int d[maxn],cnt[maxn];//划分数
int a[maxn],b[maxn],ind[maxn];
bool cmp(int x,int y){
if(b[x]==b[y])return a[x]>a[y];
return b[x]>b[y];
}
void calc(int m){
for(int i=1;i<=n;i++){
a[i]=lower_bound(d+1,d+m+1,l[i])-d;
b[i]=upper_bound(d+1,d+m+1,r[i])-d-1;
ind[i]=i;
}
for(int i=1;i<=m;i++)cnt[i]=d[i];
sort(ind+1,ind+n+1,cmp);
int it=m;
for(int i=1;i<=n;i++){
int x=ind[i];
while(it>b[x]||(!cnt[it]))it--;
if(it>=a[x])cnt[it]--;
else return;
}
int lre=0;
for(int i=1;i<=m;i++)lre+=w[d[i]];
res=max(res,lre);
}
void dfs(int x,int tmp){
// cout<<"x="<<x<<endl;
if(!tmp){
calc(x-1);
return;
}
for(int i=d[x-1];i<=tmp;i++){
d[x]=i;
dfs(x+1,tmp-i);
}
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
l[i]=read(),r[i]=read();
}
for(int i=1;i<=n;i++)w[i]=read();
d[0]=1;
dfs(1,n);
if(res==-INF){
cout<<"impossible"<<endl;
}else{
printf("%lld\n",res);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
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: 3788kb
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: 3600kb
input:
2 1 1 2 2 1 1
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3792kb
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: 3788kb
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:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3808kb
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: 3728kb
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: 3772kb
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:
5939733
result:
ok single line: '5939733'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3596kb
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: 3540kb
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:
60 21 34 13 34 48 49 31 42 5 6 16 30 1 25 35 37 3 14 3 32 25 54 2 41 24 44 27 52 26 55 8 35 31 47 41 42 4 35 53 59 13 19 11 51 36 48 5 59 40 44 28 50 5 51 37 53 50 60 14 50 22 58 20 50 20 21 5 20 19 55 5 45 19 35 7 29 5 53 25 33 19 51 37 41 13 29 12 24 13 40 10 22 1 5 22 32 14 42 11 41 16 60 35 43 3...