QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#797375 | #9529. Farm Management | Sword1E1 | WA | 0ms | 3572kb | C++20 | 1.9kb | 2024-12-02 21:49:28 | 2024-12-02 21:49:33 |
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++) {
if (i == n) {
mx = max(mx,m * a[i].w);
continue;
}
int res = ans - a[i].l * a[i].w;
int now = sum - a[i].l;
int mod = m - now;
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;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3572kb
input:
5 17 2 3 4 6 1 5 8 2 4 4 3 3 7 5 5
output:
119
result:
wrong answer 1st lines differ - expected: '109', found: '119'