QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#283876 | #7744. Elevator | ckiseki# | AC ✓ | 60ms | 4948kb | C++20 | 2.2kb | 2023-12-15 17:22:13 | 2023-12-15 17:22:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define orange(a...) orange_(#a, a)
#define debug(a...) debug_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
void solve() {
int n;
int64_t k;
cin >> n >> k;
vector<tuple<int,int,int>> v(n);
for (auto &[f, w, c] : v) {
cin >> c >> w >> f;
}
ranges::sort(v, greater<>());
int64_t total_weight_one = 0;
for (auto [f, w, c] : v) {
if (w == 1) {
total_weight_one += c;
}
}
int64_t current = 0;
int64_t fnow = -1;
int64_t ans = 0;
int borrow = 0;
for (auto [f, w, c] : v) {
if (current == 0) {
fnow = f;
}
if (w == 1) {
int r = min(borrow, c);
c -= r;
borrow -= r;
total_weight_one -= c;
// debug(c, r);
// debug(borrow, total_weight_one);
}
int64_t z = min((k - current) / w, int64_t(c));
debug(f, w, c, z);
current += w * z;
if (current == k - 1) {
ans += fnow;
current = 0;
// take a weight one
if (total_weight_one >= 1) {
borrow += 1;
total_weight_one -= 1;
debug("BORROW", borrow, total_weight_one);
}
debug(k, w);
ans += f * ( (c - z) / (k / w) );
fnow = f;
current = (c - z) % (k / w) * w;
} else if (current == k) {
ans += fnow;
debug("exact", fnow);
current = 0;
ans += f * ( (c - z) / (k / w) );
current = (c - z) % (k / w) * w;
fnow = f;
} else {
debug(z, c);
}
}
if (current) {
ans += fnow;
}
cout << ans << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3484kb
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: 38ms
memory: 4420kb
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: 58ms
memory: 4948kb
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: 58ms
memory: 4664kb
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: 60ms
memory: 4680kb
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