QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #721555 | #7744. Elevator | PoorGhost | WA | 36ms | 5240kb | C++20 | 4.9kb | 2024-11-07 16:22:42 | 2024-11-07 16:22:45 |
Judging History
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 = k;
int op = 0;
while (q1.size() || q2.size())
{
int cnt = 0;
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 == k) op = res;
int number = num / k;
if (number > 0)
{
ans += res * number;
}
int yu = num % k;
if (weight > yu)
{
weight -= yu;
}
else
{
ans += op;
weight = k - (yu - weight);
if (weight != k) 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 == k) op = res;
int number = num * 2 / k;
if (number > 0)
{
ans += res * number;
}
int yu = num * 2 - number * k;
if (weight > yu)
{
weight -= yu;
}
else
{
ans += op;
int kkksc = yu - weight;
if (kkksc & 1) kkksc--;
weight = k - kkksc;
if (weight != k) op = res;
else op = 0;
}
}
// op = max(op, res);
// if (cnt > 0)
// {
// ans += op * cnt;
// if (!weight)
// op = 0;
// else op = res;
// }
// cout << "ans = " << ans << endl;
continue;
}
if (q2.size())
{
int f = q2.top().first;
int num = q2.top().second;
q2.pop();
res = max(res, f);
if (weight == k) op = res;
int number = num * 2 / k;
if (number > 0)
{
ans += res * number;
}
int yu = num * 2 - number * k;
if (weight > yu)
{
weight -= yu;
}
else
{
ans += op;
int kkksc = yu - weight;
if (kkksc & 1) kkksc--;
weight = k - kkksc;
if (weight != k) op = res;
else op = 0;
}
// op = max(op, res);
// if (cnt > 0)
// {
// ans += op * cnt;
// if (!weight)
// op = 0;
// else op = res;
// }
// cout << "ans = " << ans << endl;
continue;
}
if (q1.size())
{ //用w为1的
int f = q1.top().first;
int num = q1.top().second;
q1.pop();
res = max(res, f);
if (weight == k) op = res;
int number = num / k;
cnt += number;
int yu = num % k;
if (weight > yu)
{
weight -= yu;
}
else
{
ans += op;
weight = k - (yu - weight);
if (weight != k) op = res;
else op = 0;
}
// op = max(op, res);
// if (cnt > 0)
// {
// ans += op * cnt;
// if (!weight)
// op = 0;
// else op = res;
// }
// cout << "ans = " << ans << endl;
}
// cout << "res = " << res << endl;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
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: -100
Wrong Answer
time: 36ms
memory: 5240kb
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 5 4 1 8 5 5 7 1 3 23 6 3 3 2 2 2 3 8 1 5 6 9 11 146 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 20 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:
wrong answer 16th lines differ - expected: '6', found: '5'