QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678423 | #9529. Farm Management | ucup-team1769# | WA | 0ms | 3512kb | C++20 | 2.2kb | 2024-10-26 14:55:27 | 2024-10-26 14:55:28 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <array>
#include <cstring>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
using i64 = long long;
const int N = 2e5 + 7;
const int M = 100;
void solve()
{
i64 n, m;
cin >> n >> m;
vector<i64> w(n + 1), l(n + 1), r(n + 1);
i64 all = m, ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> w[i] >> l[i] >> r[i];
all -= l[i];
ans += w[i] * l[i];
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(ord.begin(), ord.end(), [&](int x, int y) -> bool
{ return w[x] < w[y]; });
vector<i64> sum(n + 3), cnt(n + 3);
for (int i = n; i >= 1; i--)
{
sum[i] = sum[i + 1] + w[ord[i - 1]] * (r[ord[i - 1]] - l[ord[i - 1]]);
cnt[i] = cnt[i + 1] + r[ord[i - 1]] - l[ord[i - 1]];
}
i64 lastans = 0;
// cerr << ans << ' ' << all << '\n';
for (int t = 0; t < n; t++)
{
int k = t + 1;
int i = ord[t];
// modify i -> [0,m]
i64 used = ans, used_all = all;
used -= l[i] * w[i];
used_all += l[i];
// cerr<<i<<' ' << l[i] << '\n';
// cerr << used_all << '\n';
int lb = 1, rb = n, res = -1;
while (lb <= rb)
{
int mid = (lb + rb) >> 1;
if (cnt[mid] <= used_all)
{
res = mid;
rb = mid - 1;
}
else
{
lb = mid + 1;
}
}
// cerr << res << '\n';
if (res <= k)
{
used += sum[k + 1];
used += w[i] * (used_all - cnt[k + 1]);
}
else
{
used += sum[res];
// cerr<<"ok: " << res << '\n';
if (res - 2 >= 0)
used += w[ord[res - 2]] * (used_all - cnt[res]);
}
lastans = max(lastans, used);
}
cout << lastans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3512kb
input:
5 17 2 3 4 6 1 5 8 2 4 4 3 3 7 5 5
output:
109
result:
ok single line: '109'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3468kb
input:
12 62 503792 9 10 607358 1 3 600501 10 10 33249 4 4 774438 6 6 197692 3 6 495807 8 8 790225 5 9 77272 3 8 494819 4 9 894779 3 9 306279 5 6
output:
44007019
result:
wrong answer 1st lines differ - expected: '35204500', found: '44007019'