QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#769725#9529. Farm ManagementyimgWA 0ms3852kbC++202.2kb2024-11-21 19:07:332024-11-21 19:07:33

Judging History

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

  • [2024-11-21 19:07:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3852kb
  • [2024-11-21 19:07:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
struct Fenwick{
    int n;
    vector<i64> a;
    Fenwick(int _n = 0){
        init(_n);
    }
    void init(int _n){
        n = _n;
        a.assign(n + 1, i64{});
    }
    void add(int x, i64 v){
        for(int i = x; i <= n; i += i & -i){
            a[i] = a[i] + v;
        }
    }
    i64 sum(int x){
        i64 ans{};
        for(int i = x; i; i -= i & -i){
            ans = ans + a[i];
        }
        return ans;
    }
    i64 rangeSum(int l, int r){
        return sum(r) - sum(l - 1); 
    }
    int select(i64 k){
        int x = 0;
        i64 cur{};
        for(int i = 1 << __lg(n); i != 0; i /= 2){
            if(x + i <= n && cur + a[x + i] < k){
                x += i;
                cur = cur + a[x];
            }
        }
        return x;
    }
};
const int inf = 0x3f3f3f3f;
void work(){
    i64 n, m;
    cin >> n >> m;
    vector<array<int, 3>> a(n);
//    cout << n << "\n";
    for(int i = 0; i < n; ++i){
        
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    // cout << a[0][0] << "\n";
    sort(a.begin(), a.end(), [](const auto &A, const auto &B){
    	return A[0] > B[0];
	});
    
    Fenwick val(n + 1), pre(n + 1);
    i64 ans = 0, t = m;
//     cout << ans << "\n";
    for(int i = 0; i < n; ++i){
        ans += 1LL * a[i][1] * a[i][0];
        t -= a[i][1];
        pre.add(i + 1, a[i][2] - a[i][1]);
        val.add(i + 1, 1LL * (a[i][2] - a[i][1]) * a[i][0]);
    }
    
    i64 tmp = ans;
    ans += t * a[0][0];
//    cout << ans << "\n";
    for(int i = 1; i < n; ++i){
        pre.add(i + 1, m - a[i][2] + a[i][1]);
        
        i64 nid = pre.select(t + a[i][1]);
//        cout << "HHH : " << val.rangeSum(1, nid - 1) << " ";
//        cout << " NNN : " << nid << "\n";
		nid = max(1LL, nid);
        i64 res = tmp - 1LL * a[i][1] * a[i][0] + val.rangeSum(1, nid - 1) + (t + a[i][1] - pre.rangeSum(1, nid - 1)) * a[nid][0];
//        cout << i << "\n";
        ans = max(res, ans);
        
        pre.add(i + 1, a[i][2] - m - a[i][1]);
    }
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--)
        work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

34681730

result:

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