QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#701655	#8936. Team Arrangement	rikka_lyly^#	WA	0ms	3884kb	C++20	2.1kb	2024-11-02 14:29:26	2024-11-02 14:29:28

Judging History

你现在查看的是最新测评结果

[2024-11-02 14:29:28]
评测

测评结果：WA
用时：0ms
内存：3884kb

查看

[2024-11-02 14:29:26]
提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f

void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> pr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> pr[i].first >> pr[i].second;
    }
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    sort(pr.begin(), pr.end());
    map<ll, ll> dp;
    dp[(1ll << n) - 1] = 0;
    ll lst = INF;
    while (lst != 0)
    {
        auto it = dp.lower_bound(lst);
        if(it == dp.begin())
            break;
        it = prev(it);
        auto [state, val] = *it;
        if(state == 0)
            break;
        // cerr << "state=" << state << " val=" << val << endl;
        int biggest = 0;
        for (int i = 0; i < n; i++)
        {
            if(state >> i & 1)
                biggest = i;
        }
        int bl = pr[biggest].first, br = pr[biggest].second;
        for (int x = bl; x <= br; x++)
        {
            vector<pair<int, int>> temp;
            for (int i = 0; i < n; i++)
            {
                if (!(state >> i & 1))
                    continue;
                if (i == biggest)
                    continue;
                if(pr[i].second >= x)
                    temp.push_back({pr[i].first, i});
            }
            sort(temp.begin(), temp.end(), greater<pair<int, int>>());
            if(temp.size() < x - 1)
                continue;
            ll newstate = state ^ (1ll << biggest);
            for (int i = 0; i < x - 1; i++)
            {
                newstate ^= (1ll << temp[i].second);
            }
            if(dp.contains(newstate))
                dp[newstate] = max(dp[newstate], val + w[x]);
            else
                dp[newstate] = val + w[x];
        }
        lst = state;
    }
    if(!dp.contains(0))
        cout << "impossible\n";
    else
        cout << dp[0] << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3640kb

input:

output:

result:

ok single line: '9'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3844kb

input:

output:

result:

ok single line: '100'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3632kb

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

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

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

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

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

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

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

memory: 3884kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

output:

impossible

result:

ok single line: 'impossible'

Test #14:

score: -100

Wrong Answer

time: 0ms

memory: 3644kb

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:

-93364175

result:

wrong answer 1st lines differ - expected: '-87758107', found: '-93364175'