QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#797378 | #9529. Farm Management | Sword1E1 | WA | 0ms | 3844kb | C++20 | 1.9kb | 2024-12-02 21:51:31 | 2024-12-02 21:51:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define dbg(x...) \
do { \
std::cout << #x << " -> "; \
err(x); \
} while (0)
void err() {
std::cout << std::endl;
}
template<class T, class... Ts>
void err(T arg, Ts &... args) {
std::cout << fixed << setprecision(10) << arg << ' ';
err(args...);
}
const int maxn = 1e5 + 5;
struct node {
int w,l,r;
bool operator < (const node & b) const {
return w < b.r;
}
}a[maxn];
void GENSHEN_START() {
int n,m;cin >> n >> m;
for (int i = 1;i <= n;i++) {
cin >> a[i].w >> a[i].l >> a[i].r;
}
sort (a + 1,a + 1 + n);
int sum = 0;
for (int i = 1;i <= n;i++) {
sum += a[i].l;
}
vector <int> suf (n + 1),suf_val(n + 1);
for (int i = n;i >= 1;i--) {
if (i == n) {
suf[i] = (a[i].r - a[i].l);
suf_val[i] = (a[i].r - a[i].l) * a[i].w;
continue;
}
suf[i] = suf[i + 1] + (a[i].r - a[i].l);
suf_val[i] = (a[i].r - a[i].l) * a[i].w + suf_val[i + 1];
}
int ans = 0,mx = 0;
for (int i = 1;i <= n;i++) {
ans += a[i].w * a[i].l;
}
mx = max(mx,ans);
for (int i = 1;i <= n;i++) {
int res = ans - a[i].l * a[i].w;
int now = sum - a[i].l;
int mod = m - now;
if (i == n) {
mx = max(mx,res + mod * a[i].w);
continue;
}
int w = upper_bound(suf.rbegin(),suf.rbegin() + (n - i),mod) - suf.rbegin();
// dbg(num);
//dbg(i,w);
if (w == 0) {
res += mod * a[n - w].w;
}
else {
res += suf_val[n - w + 1] + (mod - suf[n - w + 1]) * a[n - w].w;
}
mx = max(mx,res);
//dbg(i,mx,res);
}
cout << mx << '\n';
}
// 2 3 4
// 4 3 3
// 6 1 5
// 7 5 5
// 8 2 4
// 3 10
// 2 3 6
// 6 3 3
// 8 3 4
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
int T = 1;
//cin >> T;
while (T--) GENSHEN_START();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
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: 3844kb
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:
34616000
result:
wrong answer 1st lines differ - expected: '35204500', found: '34616000'