QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785106#9529. Farm ManagementRFIYWA 1ms5672kbC++201.6kb2024-11-26 16:52:432024-11-26 16:52:43

Judging History

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

  • [2024-11-26 16:52:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5672kb
  • [2024-11-26 16:52:43]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

const int N = 2e5 + 10;

struct pp{
    ll w, l, r;
}p[N];

ll sum[N], val[N];

bool cmp(pp a, pp b){
    return a.w < b.w;
}

void solve(){
    ll n, m;

    cin >> n >> m;

    ll ans = 0, res = 0;

    for(int i = 1; i <= n; i ++){
        cin >> p[i].w >> p[i].l >> p[i].r;

        ans += p[i].w * p[i].l;

        res += p[i].l;
    }

    sort(p + 1, p + n + 1, cmp);

    //for(int i = 1; i <= n; i ++) cout << p[i].w << ' ' << p[i].l << ' ' << p[i].r << '\n';
    //cout << '\n';

    for(int i = n; i >= 1; i --){
        sum[i] = sum[i + 1] + p[i].r - p[i].l;
        val[i] = val[i + 1] + (p[i].r - p[i].l) * p[i].w;
    }

    ll ans1 = ans + (m - res) * p[n].w;

    for(int i = 1; i <= n; i ++){
        ll ti = m - res + p[i].l, cur = ans - p[i].w * p[i].l;
        ll l = 0, r = n + 1;

        //cout << cur << ' ';

        while(r - l > 1){
            ll mid = (l + r) / 2;

            ll k = sum[mid] + (i >= mid ? (p[i].r - p[i].l) : 0);

            if(k > ti) l = mid;
            else r = mid;
        }

        cur += val[r] + min(ti - sum[r], p[l].r - p[l].l) * p[l].w - (i >= r ? p[i].r * p[i].w : 0);

        if(ti - sum[l] > 0) cur += (ti - sum[l]) * p[i].w;

        //cout << r << ' ' << val[r] << ' ' << sum[r] << ' ' << cur << '\n';

        ans1 = max(ans1, cur);
    }

    cout << ans1 << '\n';
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);

    ll T = 1;

    //cin>>T;

    while(T--)
    {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5624kb

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: 0
Accepted
time: 0ms
memory: 5632kb

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:

35204500

result:

ok single line: '35204500'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 5672kb

input:

15 32
835418 2 3
178262 1 3
527643 2 2
519710 1 1
774544 3 3
82312 1 1
808199 1 1
809396 1 3
255882 1 3
80467 1 3
874973 1 3
813965 1 2
198275 1 2
152356 1 3
802055 1 1

output:

24921376

result:

wrong answer 1st lines differ - expected: '22000255', found: '24921376'