QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711698#9529. Farm Managementucup-team1329#WA 0ms3532kbC++201.7kb2024-11-05 13:05:382024-11-05 13:05:39

Judging History

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

  • [2024-11-05 13:05:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3532kb
  • [2024-11-05 13:05:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
#define bit1(x) __builtin_popcountll(x)
#define Pqueue priority_queue
#define lc p << 1
#define rc p << 1 | 1
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define fi first
#define se second
#define lowbit(x) (x & -x)

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> PII;

const ll mod = 1000000007;
const ll N = 1e6 + 10;
const ld eps = 1e-9;
const ll inf = 1e18;
const ll P = 131;
const ll dir[8][2] = {1, 0, 0, 1, -1, 0, 0, -1, 1, 1, 1, -1, -1, 1, -1, -1};

using A3 = std::array<ll, 3>;

void solve()
{
    ll n, m;
    cin >> n >> m;
    vector<A3> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i][0] >> a[i][1] >> a[i][2];

    sort(all1(a), [&](A3 a, A3 b)
         { return a[0] > b[0]; });

    ll sum = 0, tot = 0;
    vector<ll> f(n + 1), g(n + 1);
    for (int i = 1; i <= n; i++)
    {
        auto [l, r, w] = a[i];
        sum += l;
        tot += l * w;
        f[i] = (r - l) * w + f[i - 1];
        g[i] = r - l + g[i - 1];
    }

    ll ans = tot + a[1][0] * (m - sum);
    // cout<<ans<<"\n";
    for (int i = 2; i <= n; i++)
    {
        auto [l, r, w] = a[i];
        ll p = tot - l * w, t = m - (sum - l);
        ll pos = max(1ll * i, (ll)(upper_bound(all1(g), m - sum + l) - g.begin() - 1));
        // cout << f[pos] + w * (m - sum + l - g[pos]) << " ";
        ans = max(ans, p + f[pos] + w * (m - sum + l - g[pos]));
    }
    cout << ans << "\n";
}

int main()
{
    IOS int T = 1;
    // cin>>T;
    while (T--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3532kb

input:

5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5

output:

74

result:

wrong answer 1st lines differ - expected: '109', found: '74'