QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#711698 | #9529. Farm Management | ucup-team1329# | WA | 0ms | 3532kb | C++20 | 1.7kb | 2024-11-05 13:05:38 | 2024-11-05 13:05:39 |
Judging History
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'