QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#640821	#8936. Team Arrangement	meiqwq	TL	690ms	3864kb	C++23	1.4kb	2024-10-14 16:17:28	2024-10-14 16:17:29

Judging History

This is the latest submission verdict.

[2024-10-14 16:17:29]
Judged

Verdict: TL
Time: 690ms
Memory: 3864kb

Show

[2024-10-14 16:17:28]
Submitted

answer


#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define dow(i,j,k) for(i=j;i>=k;--i)
#define pr pair
#define mkp make_pair
#define fi first
#define se second
const int N=70;
int cnt[N],n,w[N],ans=1<<31;
vector<pr<int,int > >st[N],ed[N];
void dfs(int s,int n,int cur,int sum){
    if(s==n){
        int i,j,flg=1;
        set<pr<int,int> >S;
        if(sum<ans)return;
        rep(i,1,cur){
            for(auto v:st[i]){
                S.insert(v);
            }
            int req=i*cnt[i];
            if(S.size()<req){flg=0;break;}
            rep(j,1,req){
                set<pr<int,int> >::iterator it=S.begin();
                S.erase(it);
            }
            for(auto v:ed[i]){
                if(S.count(v)){flg=0;break;}
            }
            if(flg==0)break;
        }
        if(flg){
            ans=max(ans,sum);
        }
        return;
    }
    if(s+cur>n)return;
    int i;
    for(i=0;i*(cur+1)+s<=n;++i){
        cnt[cur+1]=i;
        dfs(s+i*(cur+1),n,cur+1,sum+i*w[cur+1]);
    }
}
int main(){//freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n;
    int i,j;
    rep(i,1,n){
        int l,r;cin>>l>>r;
        st[l].push_back(mkp(r,i));ed[r].push_back(mkp(r,i));
    }
    rep(i,1,n)cin>>w[i];
    //rep(i,1,n)w[i]=-100;
    dfs(0,n,0,0);
    if(ans>(1<<31))cout<<ans;else cout<<"impossible";
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3612kb

input:

output:

result:

ok single line: '9'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

output:

result:

ok single line: '100'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3616kb

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: 3548kb

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: 3548kb

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: 3840kb

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: 3616kb

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: 3552kb

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: 3588kb

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: 0

Accepted

time: 158ms

memory: 3568kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0

Accepted

time: 313ms

memory: 3564kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #13:

score: 0

Accepted

time: 690ms

memory: 3792kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #14:

score: 0

Accepted

time: 613ms

memory: 3564kb

input:

60
1 3
1 3
3 5
2 6
5 5
2 5
5 6
1 5
3 6
6 6
2 6
2 2
2 3
1 6
2 4
2 3
1 3
4 5
2 4
5 5
3 5
3 5
1 5
2 6
3 6
1 6
1 4
3 3
2 2
1 6
2 3
2 6
4 6
5 5
1 6
2 3
1 2
4 4
2 5
1 4
4 4
4 6
2 6
2 3
2 4
1 2
1 4
3 6
2 5
2 6
1 1
1 5
5 6
3 6
1 2
3 5
5 6
5 6
1 6
3 4
-9765941 -9284625 -9136963 -1872925 -9334679 -67293 96416...

output:

-87758107

result:

ok single line: '-87758107'

Test #15:

score: 0

Accepted

time: 472ms

memory: 3560kb

input:

60
1 1
1 4
2 2
3 4
1 2
1 2
1 4
2 3
1 4
1 2
4 4
1 3
2 4
2 2
2 3
2 4
1 4
3 4
1 2
3 3
2 3
1 1
2 4
2 4
2 4
1 2
1 2
3 3
3 4
2 3
1 3
2 4
1 2
1 3
1 2
3 4
2 2
2 4
1 3
1 1
2 4
2 3
2 3
4 4
1 2
1 4
1 2
2 4
2 3
4 4
2 4
3 4
3 4
1 1
2 3
3 4
2 4
2 3
3 4
2 2
-8959736 5094365 2567070 -9106790 9323252 -7495337 818129...

output:

67209846

result:

ok single line: '67209846'

Test #16:

score: 0

Accepted

time: 53ms

memory: 3556kb

input:

output:

154133500

result:

ok single line: '154133500'

Test #17:

score: 0

Accepted

time: 53ms

memory: 3560kb

input:

output:

281129340

result:

ok single line: '281129340'

Test #18:

score: 0

Accepted

time: 55ms

memory: 3816kb

input:

output:

191361510

result:

ok single line: '191361510'

Test #19:

score: 0

Accepted

time: 54ms

memory: 3508kb

input:

output:

-1693012

result:

ok single line: '-1693012'

Test #20:

score: 0

Accepted

time: 53ms

memory: 3556kb

input:

output:

-354498

result:

ok single line: '-354498'

Test #21:

score: 0

Accepted

time: 59ms

memory: 3556kb

input:

output:

178078620

result:

ok single line: '178078620'

Test #22:

score: 0

Accepted

time: 54ms

memory: 3560kb

input:

output:

267872880

result:

ok single line: '267872880'

Test #23:

score: 0

Accepted

time: 57ms

memory: 3620kb

input:

output:

101249576

result:

ok single line: '101249576'

Test #24:

score: 0

Accepted

time: 78ms

memory: 3812kb

input:

output:

84670208

result:

ok single line: '84670208'

Test #25:

score: 0

Accepted

time: 50ms

memory: 3600kb

input:

output:

35924238

result:

ok single line: '35924238'

Test #26:

score: 0

Accepted

time: 66ms

memory: 3780kb

input:

output:

39803807

result:

ok single line: '39803807'

Test #27:

score: 0

Accepted

time: 66ms

memory: 3624kb

input:

output:

232766818

result:

ok single line: '232766818'

Test #28:

score: 0

Accepted

time: 53ms

memory: 3624kb

input:

output:

-2774013

result:

ok single line: '-2774013'

Test #29:

score: 0

Accepted

time: 55ms

memory: 3656kb

input:

output:

-3135271

result:

ok single line: '-3135271'

Test #30:

score: 0

Accepted

time: 71ms

memory: 3616kb

input:

output:

193174547

result:

ok single line: '193174547'

Test #31:

score: 0

Accepted

time: 65ms

memory: 3556kb

input:

output:

202290067

result:

ok single line: '202290067'

Test #32:

score: 0

Accepted

time: 51ms

memory: 3624kb

input:

output:

result:

ok single line: '2785355'

Test #33:

score: 0

Accepted

time: 64ms

memory: 3624kb

input:

output:

result:

ok single line: '6626637'

Test #34:

score: 0

Accepted

time: 55ms

memory: 3556kb

input:

output:

-1006632

result:

ok single line: '-1006632'

Test #35:

score: 0

Accepted

time: 53ms

memory: 3864kb

input:

output:

-14968700

result:

ok single line: '-14968700'

Test #36:

score: 0

Accepted

time: 55ms

memory: 3820kb

input:

output:

13397614

result:

ok single line: '13397614'

Test #37:

score: 0

Accepted

time: 56ms

memory: 3816kb

input:

output:

21787020

result:

ok single line: '21787020'

Test #38:

score: 0

Accepted

time: 93ms

memory: 3664kb

input:

output:

35420991

result:

ok single line: '35420991'

Test #39:

score: 0

Accepted

time: 56ms

memory: 3560kb

input:

output:

11527150

result:

ok single line: '11527150'

Test #40:

score: 0

Accepted

time: 57ms

memory: 3620kb

input:

output:

52962660

result:

ok single line: '52962660'

Test #41:

score: 0

Accepted

time: 59ms

memory: 3596kb

input:

60
7 7
7 8
9 10
7 9
8 9
7 9
6 7
6 7
10 10
7 7
9 11
10 11
7 9
9 10
9 11
8 9
10 10
10 11
10 10
9 10
10 10
10 11
10 10
7 9
10 10
10 11
7 7
10 11
9 11
6 8
10 10
8 9
8 9
7 7
8 9
9 10
7 7
8 9
7 8
6 7
10 10
7 8
8 8
9 11
10 10
9 10
6 7
10 11
7 9
6 7
7 8
9 10
10 11
10 11
9 10
9 11
7 9
8 8
6 7
9 11
9903784 75...

output:

result:

ok single line: '7444173'

Test #42:

score: 0

Accepted

time: 55ms

memory: 3732kb

input:

60
6 13
9 9
9 12
5 12
5 13
9 9
6 9
7 14
6 14
6 13
4 9
8 12
6 9
3 8
8 11
9 14
4 7
9 11
4 12
9 12
9 10
8 12
8 11
3 8
7 9
7 14
8 10
7 9
7 12
4 13
8 14
4 11
9 14
5 12
8 14
6 10
7 11
6 12
6 8
9 10
8 12
6 9
5 12
5 8
5 13
9 9
9 14
7 13
4 12
7 11
7 11
6 13
5 10
2 11
7 8
6 14
6 9
6 11
5 12
8 10
-7135770 -612...

output:

36399356

result:

ok single line: '36399356'

Test #43:

score: 0

Accepted

time: 83ms

memory: 3808kb

input:

output:

108116159

result:

ok single line: '108116159'

Test #44:

score: 0

Accepted

time: 76ms

memory: 3512kb

input:

output:

112278556

result:

ok single line: '112278556'

Test #45:

score: 0

Accepted

time: 56ms

memory: 3564kb

input:

output:

42617774

result:

ok single line: '42617774'

Test #46:

score: 0

Accepted

time: 72ms

memory: 3600kb

input:

60
4 4
4 4
4 4
4 4
3 3
5 5
3 3
4 4
4 4
3 3
5 5
5 5
4 4
5 5
5 5
5 5
3 3
4 4
4 4
3 3
4 4
4 4
4 4
3 3
5 5
3 3
4 4
4 4
4 4
3 3
5 5
5 5
4 4
4 4
5 5
4 4
4 4
5 5
5 5
4 4
5 5
4 4
3 3
4 4
5 5
4 4
4 4
4 4
5 5
5 5
4 4
4 4
4 4
5 5
3 3
5 5
5 5
3 3
5 5
3 3
2902337 6482772 -92449 1451420 -7023253 8460311 -7289352 ...

output:

-18302868

result:

ok single line: '-18302868'

Test #47:

score: 0

Accepted

time: 150ms

memory: 3620kb

input:

60
3 4
4 5
5 6
2 3
3 4
4 5
3 3
4 4
3 4
3 4
3 5
5 6
2 3
5 5
5 6
4 5
3 4
3 3
3 4
5 6
4 5
3 5
5 5
5 5
3 5
4 6
3 5
3 4
3 3
4 4
4 5
4 4
3 5
2 4
5 6
1 1
5 5
4 6
3 4
4 4
4 4
4 6
4 5
3 5
4 5
2 3
3 5
4 5
3 4
4 6
3 4
2 4
3 3
4 4
5 5
4 5
3 4
4 5
5 5
4 5
7873169 -2034482 -5068361 -5262215 -6149325 5383141 84508...

output:

-55972594

result:

ok single line: '-55972594'

Test #48:

score: 0

Accepted

time: 201ms

memory: 3628kb

input:

60
2 6
2 6
1 6
2 6
3 8
3 5
2 5
1 3
3 6
2 3
3 7
4 8
1 4
2 3
3 6
3 4
3 5
5 8
1 3
4 5
2 8
4 5
2 6
1 6
1 4
2 6
5 6
3 5
3 6
1 4
2 3
2 4
2 7
2 8
4 5
2 3
3 5
2 5
5 7
5 6
3 5
1 5
2 8
5 6
3 7
1 4
3 7
4 8
1 6
2 3
1 5
5 5
4 7
5 5
4 8
2 4
4 5
4 6
3 5
2 3
-5678547 9840116 -8656673 156201 -9471511 -762354 -956848...

output:

129439723

result:

ok single line: '129439723'

Test #49:

score: 0

Accepted

time: 80ms

memory: 3848kb

input:

60
3 7
3 7
1 8
3 10
3 3
3 3
4 8
3 5
3 5
3 10
1 6
2 5
3 7
3 5
2 9
2 5
4 5
2 7
1 8
1 8
3 10
4 7
3 7
4 9
2 5
2 9
4 8
2 5
2 4
2 11
5 6
4 6
4 10
2 8
2 5
1 7
2 3
3 6
2 4
1 8
2 6
3 5
2 11
1 8
2 11
4 8
2 10
1 9
2 5
3 11
4 9
3 11
3 9
2 6
5 6
2 4
1 8
2 7
5 10
3 11
-4317498 4813470 239792 -7271480 9176085 -837...

output:

117420557

result:

ok single line: '117420557'

Test #50:

score: 0

Accepted

time: 78ms

memory: 3512kb

input:

60
3 19
2 5
1 4
2 17
5 7
2 7
4 19
3 5
1 13
5 18
2 7
3 11
1 9
5 8
1 3
3 9
4 6
2 11
2 10
1 11
2 7
3 7
1 20
3 14
4 12
2 7
5 17
4 9
2 4
1 11
1 8
1 10
1 9
4 17
2 19
2 5
2 5
2 5
4 10
2 10
5 5
4 20
3 18
5 11
2 3
1 4
3 14
2 20
4 5
2 19
4 4
3 9
1 20
4 8
1 16
1 14
1 16
2 10
3 11
3 18
-7004406 -4767571 1639847...

output:

33678782

result:

ok single line: '33678782'

Test #51:

score: 0

Accepted

time: 62ms

memory: 3560kb

input:

60
5 11
4 7
5 8
3 11
4 6
3 3
5 10
4 9
4 14
5 14
3 13
5 12
5 13
5 6
4 11
5 11
4 11
3 10
5 12
4 10
5 10
5 10
5 7
3 5
4 11
4 6
5 13
5 11
5 13
5 7
5 7
5 10
3 12
4 7
5 12
4 12
4 7
3 10
3 10
5 8
5 13
5 6
5 9
1 1
4 13
5 9
4 11
5 6
5 10
4 8
4 5
5 7
4 6
4 9
4 14
4 4
5 15
5 12
3 12
5 14
-1055954 -5486490 7038...

output:

74766831

result:

ok single line: '74766831'

Test #52:

score: 0

Accepted

time: 76ms

memory: 3624kb

input:

60
4 23
4 5
3 16
4 20
3 16
3 24
2 17
4 15
5 21
4 11
4 28
5 12
4 4
3 12
2 11
2 8
4 25
4 9
3 9
3 18
5 12
3 24
4 15
5 25
4 26
4 26
4 28
5 5
4 16
4 6
4 23
2 16
5 11
5 16
5 16
3 10
3 16
4 8
3 4
5 20
4 19
5 5
3 15
5 22
4 24
4 8
3 26
3 6
5 14
3 16
5 13
4 6
4 4
4 19
4 19
1 7
4 15
3 26
3 25
1 5
2746929 58110...

output:

66104265

result:

ok single line: '66104265'

Test #53:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

1
1 1
-10000000

output:

-10000000

result:

ok single line: '-10000000'

Test #54:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

1
1 1
10000000

output:

10000000

result:

ok single line: '10000000'

Test #55:

score: 0

Accepted

time: 0ms

memory: 3552kb

input:

1
1 1
-1

output:

-1

result:

ok single line: '-1'

Test #56:

score: 0

Accepted

time: 0ms

memory: 3812kb

input:

1
1 1
0

output:

result:

ok single line: '0'

Test #57:

score: 0

Accepted

time: 411ms

memory: 3848kb

input:

60
1 6
2 5
1 1
3 3
1 3
2 2
1 3
1 2
1 7
1 2
2 2
2 6
4 5
1 6
2 10
1 4
2 8
1 1
7 11
4 4
1 5
1 5
1 4
1 2
4 7
1 2
2 2
2 2
2 3
2 6
2 2
2 3
1 6
3 7
5 7
5 7
3 4
1 6
1 10
1 4
1 2
1 5
1 11
6 9
2 3
1 2
1 2
1 10
1 2
2 3
2 3
2 2
1 4
4 4
2 2
3 4
5 7
1 10
2 3
1 7
4844423 8958258 3565244 -1792980 -462605 -4408861 -...

output:

215303015

result:

ok single line: '215303015'

Test #58:

score: -100

Time Limit Exceeded

input:

60
1 7
3 10
2 4
4 12
9 14
2 3
3 3
2 3
6 9
11 11
4 5
4 4
4 6
2 2
4 10
2 4
1 2
3 7
7 8
1 4
5 9
1 6
2 11
2 2
2 2
1 7
4 8
3 6
5 7
1 4
4 5
1 1
1 4
1 2
1 5
1 3
1 4
6 7
1 9
1 13
1 3
1 2
2 15
2 3
5 6
2 11
1 1
1 5
4 8
3 3
8 10
1 1
1 12
3 7
2 7
1 3
4 10
2 3
2 4
1 3
3228021 -6123699 7168820 -329946 1163554 725...

output:

impossible