QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#619786	#8936. Team Arrangement	ucup-team4074^#	TL	990ms	3844kb	C++14	2.5kb	2024-10-07 15:23:52	2024-10-07 15:23:52

Judging History

This is the latest submission verdict.

[2024-10-07 15:23:52]
Judged

Verdict: TL
Time: 990ms
Memory: 3844kb

Show

[2024-10-07 15:23:52]
Submitted

answer

#include <bits/stdc++.h>
//#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pb push_back
using namespace std;
const int N = 65;

void solve();

signed main() {
    fast
    int t = 1;
//  cin >> t;
    while (t--) solve();
}

const int INF = 1e9;
int ans(-INF);
int n, w[N];
struct item {
    int l, r;
} a[N];

bool cmp(item x, item y) {
    return x.l <= y.l;
}


template<typename T>
class CMP {
public:
    bool operator()(T x, T y) {
        return a[x].r > a[y].r;
    }
};

priority_queue<int, vector<int>, CMP<int>> q;

int now[N], cnt;

int now_val;

int check() {
//    cout << 1 << '\n';
    int flag(1), head(1);
    while (!q.empty())q.pop();
    for (int i = 1; i <= cnt; i++) {
        while (a[head].l <= now[i] && head <= n)q.push(head), head++;
        if ((!q.empty()) && a[q.top()].r < now[i]) {
            flag = 0;
        }
        for (int j = 1; j <= now[i]; j++) {
            if (!q.empty())q.pop();
            else flag = 0;
        }
    }
    if (!q.empty() || head <= n)flag = 0;
    return flag;
}

int sta_cnt(0);

void dfs(int sum, int lim) {
    if (sum == 0) {
        if (ans < now_val) {
            if (check()) {
                ans = now_val;
            }
        }
        return;
    }
    for (int i = lim; i <= sum; i++) {
        now_val += w[i];
        ++cnt;
        now[cnt] = i;
        dfs(sum - i, i);
        cnt--;
        now_val -= w[i];
    }
    return;
}


void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i].l >> a[i].r;
    for (int i = 1; i <= n; i++)cin >> w[i];
    stable_sort(a + 1, a + n + 1, cmp);
    dfs(n, 1);
    if (ans == -INF)cout << "impossible";
    else cout << ans << '\n';
    return;
}
/*
3
2 3
1 2
2 2
4 5 100

3
1 3
3 3
2 3
1 1 100

2
1 1
2 2
1 1

3
1 2
1 2
1 2
1 100000 1

 5
1 5
1 5
1 5
1 5
1 5
-1 -1 -2 -1 -2

60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1 60
1234 124 2342 41 4 14 12 341 34 1 4 1
 1234 124 2342 41 4 14 12 341 34 1 4 1
 1234 124 2342 41 4 14 12 341 34 1 4 1
 1234 124 2342 41 4 14 12 341 34 1 4 1
 1234 124 2342 41 4 14 12 341 34 1 4 1
 */

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3484kb

input:

output:

result:

ok single line: '9'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

output:

result:

ok single line: '100'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3844kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3544kb

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

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

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:

result:

ok single line: '5939733'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3648kb

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

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: 386ms

memory: 3560kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0

Accepted

time: 801ms

memory: 3768kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #13:

score: 0

Accepted

time: 904ms

memory: 3548kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #14:

score: 0

Accepted

time: 839ms

memory: 3540kb

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: 44ms

memory: 3576kb

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: 18ms

memory: 3544kb

input:

output:

154133500

result:

ok single line: '154133500'

Test #17:

score: 0

Accepted

time: 18ms

memory: 3548kb

input:

output:

281129340

result:

ok single line: '281129340'

Test #18:

score: 0

Accepted

time: 15ms

memory: 3576kb

input:

output:

191361510

result:

ok single line: '191361510'

Test #19:

score: 0

Accepted

time: 18ms

memory: 3548kb

input:

output:

-1693012

result:

ok single line: '-1693012'

Test #20:

score: 0

Accepted

time: 18ms

memory: 3544kb

input:

output:

-354498

result:

ok single line: '-354498'

Test #21:

score: 0

Accepted

time: 14ms

memory: 3544kb

input:

output:

178078620

result:

ok single line: '178078620'

Test #22:

score: 0

Accepted

time: 18ms

memory: 3604kb

input:

output:

267872880

result:

ok single line: '267872880'

Test #23:

score: 0

Accepted

time: 122ms

memory: 3600kb

input:

output:

101249576

result:

ok single line: '101249576'

Test #24:

score: 0

Accepted

time: 466ms

memory: 3608kb

input:

output:

84670208

result:

ok single line: '84670208'

Test #25:

score: 0

Accepted

time: 450ms

memory: 3548kb

input:

output:

35924238

result:

ok single line: '35924238'

Test #26:

score: 0

Accepted

time: 408ms

memory: 3544kb

input:

output:

39803807

result:

ok single line: '39803807'

Test #27:

score: 0

Accepted

time: 112ms

memory: 3580kb

input:

output:

232766818

result:

ok single line: '232766818'

Test #28:

score: 0

Accepted

time: 151ms

memory: 3544kb

input:

output:

-2774013

result:

ok single line: '-2774013'

Test #29:

score: 0

Accepted

time: 201ms

memory: 3548kb

input:

output:

-3135271

result:

ok single line: '-3135271'

Test #30:

score: 0

Accepted

time: 316ms

memory: 3548kb

input:

output:

193174547

result:

ok single line: '193174547'

Test #31:

score: 0

Accepted

time: 176ms

memory: 3644kb

input:

output:

202290067

result:

ok single line: '202290067'

Test #32:

score: 0

Accepted

time: 100ms

memory: 3616kb

input:

output:

result:

ok single line: '2785355'

Test #33:

score: 0

Accepted

time: 167ms

memory: 3548kb

input:

output:

result:

ok single line: '6626637'

Test #34:

score: 0

Accepted

time: 148ms

memory: 3584kb

input:

output:

-1006632

result:

ok single line: '-1006632'

Test #35:

score: 0

Accepted

time: 153ms

memory: 3600kb

input:

output:

-14968700

result:

ok single line: '-14968700'

Test #36:

score: 0

Accepted

time: 154ms

memory: 3640kb

input:

output:

13397614

result:

ok single line: '13397614'

Test #37:

score: 0

Accepted

time: 441ms

memory: 3612kb

input:

output:

21787020

result:

ok single line: '21787020'

Test #38:

score: 0

Accepted

time: 317ms

memory: 3800kb

input:

output:

35420991

result:

ok single line: '35420991'

Test #39:

score: 0

Accepted

time: 934ms

memory: 3540kb

input:

output:

11527150

result:

ok single line: '11527150'

Test #40:

score: 0

Accepted

time: 579ms

memory: 3768kb

input:

output:

52962660

result:

ok single line: '52962660'

Test #41:

score: 0

Accepted

time: 990ms

memory: 3604kb

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

Time Limit Exceeded

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