QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684915#9529. Farm Managementticking_away#WA 0ms3612kbC++201.9kb2024-10-28 16:33:232024-10-28 16:33:24

Judging History

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

  • [2024-10-28 16:33:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3612kb
  • [2024-10-28 16:33:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 3e5 + 10;
const int mod = 1000000007;
#define inl inline
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
#define forall(i, a) for (auto &i : a)

/**
   ____         ___ _____
  / ___| _   _ / _ \___ /
  \___ \| | | | | | ||_ \
   ___) | |_| | |_| |__) |
  |____/ \__, |\___/____/
         |___/
*/
istream &operator>>(istream &in, vector<int> &v)
{
    for (auto &i : v)
        in >> i;
    return in;
}
ostream &operator<<(ostream &out, vector<int> &v)
{
    for (auto &i : v)
        out << i << " ";
    return out;
}
bool _output = 0;

#define int ll
struct p
{
    int w, l, r;
};
int sum[maxn];
int pre[maxn];
void solve()
{
    int n, m;
    cin >> n >> m;

    vector<p> a(n + 1);
    fr(i, 1, n) cin >> a[i].w >> a[i].l >> a[i].r;

    int now = 0;
    int now_ans = 0;
    fr(i, 1, n)
    {
        now += a[i].l;
        now_ans += a[i].w * a[i].l;
    }
    sort(a.begin() + 1, a.end(), [](p a, p b)
         { return a.w > b.w; });
    int ans = 0;

    fr(i, 1, n)
    {
        sum[i] = sum[i - 1] + a[i].r - a[i].l;
        pre[i] = pre[i - 1] + (a[i].r - a[i].l) * a[i].w;
    }

    fr(i, 1, n)
    {
        int pos = upper_bound(sum + 1, sum + i + 1, m - now + a[i].l) - sum;
        int t = now_ans + pre[i - 1] - a[i].l * a[i].w;
        t += a[min(pos, i)].w * (m + a[i].l - now - sum[pos - 1]);
        // cout << t << endl;
        ans = max(ans, t);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    if (_output)
        cin >> _;
    while (_--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

49212392

result:

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