QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#678454 | #9529. Farm Management | ucup-team1769# | WA | 0ms | 3588kb | C++20 | 2.1kb | 2024-10-26 15:01:04 | 2024-10-26 15:01:04 |
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];
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;
}
}
if (res <= k)
{
used += sum[k + 1];
used += w[i] * (used_all - cnt[k + 1]);
}
else
{
used += sum[res];
if (res - 2 >= 0)
used += w[ord[res - 2]] * (used_all - cnt[res]);
}
lastans = max(lastans, used);
}
lastans = max(lastans, ans + all * w[ord[n - 1]]);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
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: 3588kb
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'