QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#268205#7744. Elevatortonylin1026AC ✓189ms8720kbC++202.7kb2023-11-28 13:23:352023-11-28 13:23:36

Judging History

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

  • [2023-11-28 13:23:36]
  • 评测
  • 测评结果:AC
  • 用时:189ms
  • 内存:8720kb
  • [2023-11-28 13:23:35]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define ite map<int, int, greater<int>>::iterator
using namespace std;

struct node {
    int c, w, f;
};
void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int, greater<int>> mp[3];
    for (int i = 0; i < n; i++) {
        int c, w, f;
        cin >> c >> w >> f;
        if (w == 1) {
            mp[1][f] += c;
        } else
            mp[2][f] += c;
    }
    int ans = 0, last = k, nowf = 0;
    for (ite it1 = mp[1].begin(), it2 = mp[2].begin();
         it1 != mp[1].end() || it2 != mp[2].end();) {
        // cerr<<ans<<' '<<last<<' '<<nowf<<'\n';
        // cerr << (*it1).first << ' ' << (*it2).first << '\n';
        if (it1 == mp[1].end() ||
            (it2 != mp[2].end() && (*it2).first >= (*it1).first)) {
            if ((*it2).second * 2 < last) {
                nowf = max(nowf, (*it2).first), last -= (*it2).second * 2;
            } else if ((*it2).second * 2 == last) {
                ans += max(nowf, (*it2).first), nowf = 0, last = k;
            } else {
                if (last & 1) {
                    if (it1 != mp[1].end()) {
                        (*it1).second--, last--;
                        if ((*it1).second == 0) {
                            it1++;
                        }
                    }
                }
                (*it2).second -= last / 2, ans += max(nowf, (*it2).first),
                    last = k, nowf = (*it2).first;
                ans += (*it2).second / (last / 2) * nowf;
                (*it2).second %= (last / 2);
                if ((*it2).second == 0) {
                    nowf = 0;
                } else {
                    last -= (*it2).second * 2;
                }
            }
            it2++;

        } else {
            if ((*it1).second < last) {
                nowf = max(nowf, (*it1).first), last -= (*it1).second;
            } else if ((*it1).second == last) {
                ans += max(nowf, (*it1).first), nowf = 0, last = k;
            } else {
                (*it1).second -= last, ans += max(nowf, (*it1).first),
                    last = k, nowf = (*it1).first;
                ans += (*it1).second / last * nowf;
                (*it1).second %= last;
                if ((*it1).second == 0) {
                    nowf = 0;
                } else {
                    last -= (*it1).second;
                }
            }
            it1++;
        }
    }
    if (last != k) {
        ans += nowf;
    }
    cout << ans << '\n';
    return;
}
signed main() {
    // ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

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: 100ms
memory: 3592kb

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: 127ms
memory: 8500kb

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: 189ms
memory: 8720kb

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: 184ms
memory: 8712kb

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