QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#738816 | #9529. Farm Management | zxcdxw | WA | 0ms | 3492kb | C++14 | 1.4kb | 2024-11-12 20:01:31 | 2024-11-12 20:01:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define lowbit(x) (x)&(-x)
#define int long long
//#define double long double
const int N = 1e6 + 5;
const ll base = 131;
const ll mod = 998244353;
struct syz {
int a, b, c;
syz() {}
syz(int aa, int bb, int cc) :a(aa), b(bb), c(cc)
{}
bool operator <(syz x) {
if (this->a == x.a) {
return this->b < x.b;
}
return this->a > x.a;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<syz>w(n + 1);
for (int i = 1; i <= n; ++i) cin >> w[i].a >> w[i].b >> w[i].c;
sort(w.begin() + 1, w.end());
vector<int>pre(n + 1), presum(n + 1);
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + w[i].c - w[i].b, presum[i] = presum[i - 1] + (w[i].c - w[i].b) * w[i].a;
ll ma = 0, sum = 0, Sum = 0;
for (int i = 1; i <= n; ++i) {
sum += w[i].b;
Sum += w[i].b * w[i].a;
}
ma = max(ma, Sum + w[1].a * (m - sum));
for (int i = n; i >= 1; --i) {
int res = m - sum + w[i].b;
auto now = upper_bound(pre.begin() + 1, pre.end(), res) - pre.begin() - 1;
if(now+1<i)ma = max(ma, Sum - w[i].b * w[i].a + presum[now] + (res - pre[now]) * w[i].a);
}
cout << ma << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3492kb
input:
5 17 2 3 4 6 1 5 8 2 4 4 3 3 7 5 5
output:
99
result:
wrong answer 1st lines differ - expected: '109', found: '99'