QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#721649#7744. ElevatorPoorGhostAC ✓76ms6796kbC++204.6kb2024-11-07 16:31:512024-11-07 16:31:55

Judging History

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

  • [2024-11-07 16:31:55]
  • 评测
  • 测评结果：AC
  • 用时：76ms
  • 内存：6796kb
查看
  • [2024-11-07 16:31:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e5 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, k;
void solve()
{
    cin >> n >> k;
    priority_queue<pii, vector<pii>, less<pii>>q1, q2;
    for (int i = 1, c, w, f; i <= n; i++)
    {
        cin >> c >> w >> f;
        if (w == 1)
        {
            q1.push({f, c});
        }
        else q2.push({f, c});
    }
    int ans = 0;
    int weight = 0;
    int op = 0;
    while (q1.size() || q2.size())
    {
        int res = 0;
        if (q1.size() && q2.size())
        {
            if (q1.top().first > q2.top().first)
            {   //用w为1的
                int f = q1.top().first;
                int num = q1.top().second;
                q1.pop();
                res = max(res, f);

                if (weight == 0) op = res;

                int number = num / k;
                if (number > 0)
                {
                    ans += res * number;
                }

                int yu = num % k;

                if (weight + yu < k)
                {
                    weight += yu;
                }
                else
                {
                    ans += op;
                    weight += yu;
                    weight -= k;
                    if (weight != 0) op = res;
                    else op = 0;
                }
            }
            else
            {   //用w为2的
                int f = q2.top().first;
                int num = q2.top().second;
                q2.pop();
                res = max(res, f);

                if (weight == 0) op = res;

                int number = (num * 2) / k;
                if (number > 0)
                {
                    ans += res * number;
                }

                int yu = num * 2 - number * k;

                if (weight + yu < k)
                {
                    weight += yu;
                }
                else
                {
                    ans += op;
                    int kkksc = k - weight;
                    if (kkksc & 1)
                    {
                        if (q1.size())
                        {
                            int tmpf = q1.top().first;
                            int tmpnum = q1.top().second;
                            q1.pop();
                            tmpnum--;
                            if (tmpnum > 0)
                                q1.push({tmpf, tmpnum});
                        }
                        kkksc--;
                    }
                    weight = yu - kkksc;
                    if (weight != 0) op = res;
                    else op = 0;
                }
            }
            continue;
        }
        if (q2.size())
        {
            int f = q2.top().first;
            int num = q2.top().second;
            q2.pop();
            res = max(res, f);

            if (weight == 0) op = res;

            int number = (num * 2) / k;
            if (number > 0)
            {
                ans += res * number;
            }

            int yu = num * 2 - number * k;

            if (weight + yu < k)
            {
                weight += yu;
            }
            else
            {
                ans += op;
                int kkksc = k - weight;
                if (kkksc & 1)
                {
                    kkksc--;
                }
                weight = yu - kkksc;
                if (weight != 0) op = res;
                else op = 0;
            }
            continue;
        }
        if (q1.size())
        {   //用w为1的
            int f = q1.top().first;
            int num = q1.top().second;
            q1.pop();
            res = max(res, f);

            if (weight == 0) op = res;

            int number = num / k;
            if (number > 0)
            {
                ans += res * number;
            }

            int yu = num % k;

            if (weight + yu < k)
            {
                weight += yu;
            }
            else
            {
                ans += op;
                weight += yu;
                weight -= k;
                if (weight != 0) op = res;
                else op = 0;
            }
        }
    }
    if (weight > 0) ans += op;
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3472kb

input:

2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345

output:

24
100000

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 45ms
memory: 5252kb

input:

5501
8 104
5 2 3
6 2 4
5 2 3
6 2 9
8 2 4
2 1 3
7 2 4
8 2 8
1 290
3 1 1
12 12
6 1 2
1 2 2
1 1 2
1 2 4
6 1 1
1 2 5
6 1 4
4 1 4
6 2 4
6 2 5
4 2 5
4 1 4
5 334
1 1 4
1 2 3
4 2 1
5 1 1
2 1 2
13 218
5 2 3
5 1 4
1 2 1
1 2 5
3 2 2
1 1 3
4 2 2
1 2 5
2 2 1
2 1 5
3 2 1
5 2 1
1 1 4
10 260
7 2 1
5 1 1
5 2 4
6 1 6...

output:

9
1
23
4
5
7
1
3
9
6
1
10
4
9
17
6
4
1
8
5
5
7
1
3
23
6
3
3
2
2
2
3
8
1
5
6
9
11
147
7
10
2
7
7
8
6
5
5
1
7
3
5
10
7
7
10
8
1
4
2
3
9
1
5
2
9
1
6
7
7
6
10
18
8
10
4
10
9
2
8
3
5
9
3
6
5
3
2
6
1
3
2
2
1
6
9
6
3
4
8
9
9
2
6
1
2
6
7
5
2
5
21
8
1
2
3
4
9
3
4
6
5
9
6
1
7
3
7
3
2
2
8
7
3
5
9
7
10
7
3
2
4
...

result:

ok 5501 lines

Test #3:

score: 0
Accepted
time: 72ms
memory: 6796kb

input:

3
100000 8
8 2 6
7 2 8
5 1 10
7 2 7
4 1 7
6 2 9
7 1 2
3 1 1
5 1 10
5 1 1
3 2 10
5 2 5
7 1 6
5 2 7
7 2 1
5 1 6
2 2 10
8 1 7
7 1 1
10 2 6
9 1 1
8 1 4
10 1 4
6 1 1
4 1 4
1 2 9
3 2 6
6 1 3
4 1 7
9 2 5
8 2 4
7 2 1
2 2 10
6 2 9
3 1 3
2 2 3
2 2 4
7 2 4
8 1 1
5 2 3
5 2 7
7 2 9
1 1 4
5 1 2
2 1 9
3 2 1
9 2 2
...

output:

568601
4708350936
93900404329230

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 76ms
memory: 6584kb

input:

3
100000 174
90429 1 64237
30851 1 44358
63571 2 89174
20391 2 28747
13561 2 88689
81508 2 28383
85733 1 5777
37524 2 34730
10588 2 88519
61493 2 83682
55885 1 65270
17669 2 63015
85387 1 64757
91420 2 74020
9067 2 91750
20809 1 52771
36478 2 17941
62064 1 36433
72912 2 6100
53923 2 73971
65825 2 39...

output:

2156004461915
884586357480
59034901233

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 67ms
memory: 6140kb

input:

3
100000 4418822
19907 1 13081
59730 2 93611
35050 1 5867
87777 1 21890
18374 1 82418
79526 2 76106
33510 2 45826
75573 1 42240
35449 1 98727
80720 2 65290
32021 2 51348
52399 2 97828
75498 2 51728
89905 1 22825
2855 1 26204
11427 1 99583
55530 2 37895
22256 2 92230
19533 1 9142
16138 1 54018
53102 ...

output:

84699074
270668
100000

result:

ok 3 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-11-30 20:44:52 | OpenSource Project