QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694336 | #9529. Farm Management | YuLan | WA | 1ms | 7064kb | C++20 | 1.4kb | 2024-10-31 17:44:06 | 2024-10-31 17:44:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
struct node
{
ll w,l,r;
node() : w(0), l(0), r(0) {}
node(ll w1,ll l1,ll r1)
{
w = w1;
l = l1;
r = r1;
}
bool operator < (const node & a) const
{
return w > a.w;
}
};
node b[N];
ll suml[N],sumd[N],sumindex[N],sumLsum[N];
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
ll n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
ll w1,l1,r1;
cin>>w1>>l1>>r1;
b[i] = node(w1,l1,r1);
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
suml[i] = suml[i-1] + b[i].l;
sumd[i] = sumd[i-1] + (b[i].r - b[i].l)*b[i].w;
sumindex[i] = sumindex[i-1] + (b[i].r - b[i].l);
sumLsum[i] = sumLsum[i-1] + b[i].l * b[i].w;
}
ll ans = 0;
for(int i=1;i<=n;i++)
{
ll length = m - (suml[n] - suml[i])-suml[i-1];
ll now = sumLsum[i-1];
if(sumindex[i-1]<=length)
{
now += sumd[i-1] + b[i].w * (length - sumindex[i-1]);
}else{
int pos = upper_bound(sumindex,sumindex+i,length) - sumindex - 1;
now += sumd[pos-1] + (length - sumindex[pos-1])*b[pos].w;
}
ans = max(ans,now);
}
cout<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7056kb
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: 1ms
memory: 7064kb
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:
33742992
result:
wrong answer 1st lines differ - expected: '35204500', found: '33742992'