QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694218#9529. Farm Managementcrychic#WA 0ms3552kbC++171.7kb2024-10-31 17:29:212024-10-31 17:29:24

Judging History

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

  • [2024-10-31 17:29:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3552kb
  • [2024-10-31 17:29:21]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;



void solve() {
    ll n,m;
    cin >> n >> m;
    vector<array<ll,3>> a(n + 1);
    for(int i = 1;i <= n;i ++){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    sort(a.begin() + 1,a.end());
    vector<ll> preL(n + 2),sufR(n + 2),preLw(n + 2),sufRw(n + 2);
    for(int i = 1;i <= n;i ++){
        preL[i] = preL[i - 1] + a[i][1];
        preLw[i] = preLw[i - 1] + a[i][0] * a[i][1];
    }
    sufRw[n] = a[n][0] * a[n][2];
    sufR[n] = a[n][2];
    for(int i = n - 1;i >= 1;i --){
        sufR[i] = sufR[i + 1] + a[i][2];
        sufRw[i] = sufRw[i + 1] + a[i][0] * a[i][2];
    }
    ll ans = 0;
    for(int i = 1;i <= n;i ++){
        ll tmp = preL[i - 1] + sufR[i + 1];
        if(tmp <= m){
            ans = max(ans,preLw[i - 1] + sufRw[i + 1] + a[i][0] * (m - tmp));
        }else {
            int l = 1, r = n;
            while(l + 1 < r){
                int mid = l + r >> 1;
                ll res = preL[mid] + sufR[mid + 1] - a[i][1];
                if(res <= m)l = mid;
                else r = mid;
            }
            ll cnt = m - (preL[l] + sufR[l + 1] - a[i][1]);
            // cout << i << ' ' << l << ' ' << cnt  << '\n';
            // cout << 
            // assert(cnt >= 0 && cnt < a[i][2] - a[i][1]);
            ll ress = preLw[l] + sufRw[l + 1] - a[i][0] * a[i][1] + cnt * a[l][0];
            ans = max(ans,ress); 
        }

    }
    cout << ans << '\n';
    // for(int i = 1;i <= n;i ++)
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int t = 1;
    // cin >> t;b
    while(t -- ) {
        solve();
    }
    
    return 0;
}

詳細信息

Test #1:

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

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

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'