QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#701643#9529. Farm Managementfosov#WA 0ms3740kbC++141.4kb2024-11-02 14:28:312024-11-02 14:28:32

Judging History

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

  • [2024-11-02 14:28:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3740kb
  • [2024-11-02 14:28:31]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;

#define ll long long 
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>

#define N 100010

ll sz[N], w[N], rem[N], psum[N];
tuple<int, int, int> a[N];

int bsl(int l, int r, ll x) {
    while (l < r) {
        int m = (l + r) >> 1;
        if (sz[m] <= x) {
            l = m+1;
        } else {
            r = m;
        }
    }
    return r - 1;
}

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n, m; cin >> n >> m;

    ll mm = 0, mw = 0;
    for (int i = 1; i <= n; ++ i) {
        int w, l, r; cin >> w >> l >> r;
        a[i] = make_tuple(w, l, r);

        mm += l;
        mw += 1ll * l * w;
    }
    sort(a+1, a+n);
    reverse(a+1, a+n);

    for (int i = 1; i <= n; ++ i) {
        auto& [_w, _l, _r] = a[i];
        w[i] = _w;;
        rem[i] = _r - _l;
        sz[i] = rem[i] + sz[i-1];
        psum[i] = rem[i] * w[i] + psum[i-1];
    }

    ll res = 0;
    for (int i = 1; i <= n; ++ i) {
        auto& [_w, _l, _r] = a[i];

        ll pm = m - (mm - _l);
        ll cw = mw - 1ll * _l * _w;

        int idx = bsl(0, i, pm);
        ll contr = psum[idx] + w[i] * (pm - sz[idx]);
        res = max(res, cw + contr);
    }

    cout << res << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

34859047

result:

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