QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#600766 | #7744. Elevator | E7k | WA | 42ms | 7724kb | C++20 | 3.1kb | 2024-09-29 19:00:18 | 2024-09-29 19:00:19 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define gcd __gcd
using namespace std;
typedef pair<int,int> pii;
const int INF = 9e18;
const int inf = 2e9;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
// int tt = t;
// int u = 0;
while(t --)
{
// u ++;
int n,k;
cin >> n >> k;
vector<array<int,3>> a;
for(int i = 1;i <= n;i ++)
{
int f,c,w;
cin >> c >> w >> f;
// a[i] = {f,c,w};
if(c > 0)
{
a.push_back({f,c,w});
}
}
sort(a.begin(),a.end());
int ans = 0;
vector<int> res;
n = a.size() - 1;
for(int i = 0;i < a.size();i ++)
{
if((a[i][2] & 1))
{
res.push_back(i);
}
}
int sum = 0,lst = 0;
for(int i = n,j = n;i >= 0;i --)
{
while(j >= 0 && a[j][1] <= 0) j --;
if(sum + a[i][1] * a[i][2] <= k)
{
sum += a[i][1] * a[i][2];
if(sum == k || i == 0)
{
ans += a[j][0];
j = i - 1;
sum = 0;
}
continue;
}
int tep = (k - sum) / a[i][2] * a[i][2];
lst = a[i][1] * a[i][2] - tep;
sum += tep;
if(sum < k)
{
while(res.size() && a[res.back()][0] >= a[i][0]) res.pop_back();
if(res.size())
{
auto x = res.back();
if(a[x][1] == 0)
{
res.pop_back();
continue;
}
a[x][1] --;
if(a[x][1] == 0) res.pop_back();
// res.pop_back();
}
}
// if(i == 1) cout << ans << endl;
ans += a[j][0];
// if(i == 1) cout << 'y' << ans << endl;
if(lst >= k)
{
int cnt = lst / k;
ans += cnt * a[i][0];
int x = cnt * a[i][0];
while(res.size() && a[res.back()][0] >= a[i][0]) res.pop_back();
while(x < k && cnt && res.size())
{
int y = res.back();
if(cnt >= a[y][1])
{
res.pop_back();
cnt -= a[y][1];
}
else a[y][1] -= cnt;
}
lst %= k;
}
// if(i == 1)
// cout << ans << ' ' << sum << endl;
sum = lst;
if(sum > 0) j = i;
else j = i - 1;
// while(j >= 0 && a[j][1] <= 0) j --;
if(i == 0 && sum > 0) ans += a[i][0];
// if(i == 1)
// cout << ans << ' ' << sum << endl;
}
cout << ans << endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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: 42ms
memory: 7724kb
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:
wrong answer 226th lines differ - expected: '92', found: '91'