QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684173#9529. Farm ManagementWanShiWA 0ms3716kbC++141.7kb2024-10-28 11:05:342024-10-28 11:05:34

Judging History

你现在查看的是最新测评结果

  • [2024-10-28 11:05:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3716kb
  • [2024-10-28 11:05:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e5 + 5;
int __ = 1, n = 0, m;
string s;
int valr[N], vall[N], vr[N];
struct ifo
{
    int l, r, w;
    bool operator<(const ifo &a) const
    {
        return w > a.w;
    }
} info[N];
int sumr = 0, suml = 0;
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> info[i].w >> info[i].l >> info[i].r;
        sumr += info[i].r;
        suml += info[i].l;
    }
    info[0] = {0, 0, 0};
    sort(info + 1, info + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += info[i].l * info[i].w;
        valr[i] = valr[i - 1] + info[i].r * info[i].w;
        vall[i] = vall[i - 1] + info[i].l * info[i].w;
        vr[i] = vr[i - 1] + info[i].r - info[i].l;
    }
    ans += (m - suml) * info[1].w;
    for (int i = 1; i <= n; i++)
    {
        if (sumr - info[i].r <= m)
        {
            ans = max(ans, (valr[i] - info[i].r * info[i].w) - info[i].w * (m - (sumr - info[i].r)));
            continue;
        }
        int l = 0, r = i - 1;
        while (l < r)
        {
            int mid = (l + r + 1) / 2;
            if (vr[mid] <= info[i].l)
                l = mid;
            else
                r = mid - 1;
        }
        int tans = 0;
        if (l + 1 < i)
            tans += (info[i].l - vr[l]) * info[l + 1].w;
        tans += valr[l] + (vall[n] - vall[l] - info[i].l * info[i].w);
        ans = max(ans, tans);
    }
    cout << ans << endl;
    return;
}
int32_t main()
{
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __;
    while (__--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

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: 3716kb

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:

34309721

result:

wrong answer 1st lines differ - expected: '35204500', found: '34309721'