QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#678454#9529. Farm Managementucup-team1769#WA 0ms3588kbC++202.1kb2024-10-26 15:01:042024-10-26 15:01:04

Judging History

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

  • [2024-10-26 15:01:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3588kb
  • [2024-10-26 15:01:04]
  • 提交

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'