QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#745849#9529. Farm ManagementDung1604WA 0ms3856kbC++201.9kb2024-11-14 11:59:522024-11-14 11:59:52

Judging History

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

  • [2024-11-14 11:59:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2024-11-14 11:59:52]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int long long
#define inf 10000000000000000
struct crop{
    ll w, l, r;
};
ll pos[100005];
ll Time[100005];
ll prefix[100005];
void solve(){
    int n, m;
    cin >>n  >> m;
    vector<crop> harvest(n+ 1);
    vector<pair<ll, ll>> add(n +1);
    for(int i = 1; i <= n; i++){
        cin >> harvest[i].w >> harvest[i].l >> harvest[i].r;
    }
    ll init = 0;
    ll remain = m;
    for(int i = 1; i <= n; i++){
        init += harvest[i].w*harvest[i].l;
        remain -= harvest[i].l;
    }
    for(int i = 1; i <= n; i++){
        add[i] = {harvest[i].w,i};
    }
    sort(add.begin() + 1, add.end(), greater<pair<ll,ll>>());
    for(int i = 1; i <= n; i++){
        pos[add[i].second] = i;
        Time[i] = Time[i - 1] + harvest[add[i].second].r - harvest[add[i].second].l;
        prefix[i] = prefix[i-1] + (harvest[add[i].second].r - harvest[add[i].second].l)*add[i].first;
    }
    ll ans = init;
    for(int i = 1;i <= n; i++){
        
        ll cur = init;
        cur -= harvest[i].l*harvest[i].w;
        ll used = remain + harvest[i].l;
        int lo = 1;
        int hi = n;
        int p = -1;
        
        while(lo <= hi){
            int mid = (lo + hi)/2;
            if(Time[mid] <= used){
                p = mid;
                lo = mid + 1;

            }
            else{
                hi = mid - 1;
            }
        }
        if(pos[i] > p){
            ans = max(ans, cur + prefix[p-1] + add[p].first*(used - Time[p-1]));
            
            
        }
        else{
            int x = pos[i];
            ans = max(ans, cur + prefix[x-1] + add[x].first*(used - Time[x-1]));
        }
    }
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    solve();
    
    
     
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

140286560772459

result:

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