QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692324#9529. Farm Managementwangshengzhe#WA 1ms5704kbC++141.9kb2024-10-31 14:19:362024-10-31 14:19:40

Judging History

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

  • [2024-10-31 14:19:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5704kb
  • [2024-10-31 14:19:36]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
using LL = long long;
using ll = long long;

const int N = 2E5 + 10;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double ef = 1e-12;
const double PI = acos(-1);

#define rep(i,a,b) for(int i = a;i<=b;i++)
#define pre(i,a,b) for(int i = a;i>=b;i--)
#define int long long

int n, m;
struct node {
    int le, ri;
    int w;
};
node p[100005];
node qian[100005], ho[100005];

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

int find1(int le, int ri, int tar)
{
    int pp = le - 1;
    while (le < ri)
    {
        int mid = (le + ri) >> 1;
        if (ho[mid].ri + qian[mid - 1].le - qian[pp].le <= tar) ri = mid;
        else le = mid + 1;
    }
    return le;
}

void solve()
{
    cin >> n >> m;
    rep(i, 1, n) {
        cin >> p[i].w >> p[i].le >> p[i].ri;
    }
    sort(p + 1, p + n + 1, cmp);
    rep(i, 1, n)
    {
        qian[i].le = qian[i - 1].le + p[i].le;
        qian[i].w = qian[i - 1].w + p[i].w * p[i].le;
    }
    pre(i, n, 1)
    {
        ho[i].ri = ho[i + 1].ri + p[i].ri;
        ho[i].w = ho[i + 1].w + p[i].w * p[i].ri;
    }
    int ans = 0;
    rep(i, 1, n)
    {
        int pp = find1(i + 1, n + 1, m - qian[i - 1].le);
        int an;
        if (pp - 2 >= i) an = ho[pp].w + qian[pp - 2].w - p[i].w * p[i].le + (m - qian[pp - 2].le - ho[pp].ri + p[i].le) * p[pp - 1].w;
        else an = ho[pp].w + qian[pp - 2].w + (m - qian[pp - 2].le - ho[pp].ri) * p[pp - 1].w;
        ans = max(ans, an);
    }
    pre(i, n, 1)
    {
        int an = qian[i - 1].w + ho[i + 1].w + (m - qian[i - 1].le - ho[i + 1].ri) * p[i].w;
        ans = max(ans, an);
    }
    cout << ans << endl;
    return;
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int 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: 0ms
memory: 5704kb

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: 1ms
memory: 5688kb

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'