QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#682811 | #9529. Farm Management | ChiTang | WA | 1ms | 5716kb | C++14 | 2.3kb | 2024-10-27 17:25:32 | 2024-10-27 17:25:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
struct node
{
int w, l, r;
};
node a[N];
bool cmp(node x, node y)
{
return x.w > y.w;
}
int pre[N];
int val[N];
int ti;
int flag = 0;
bool check(int x)
{
if (flag <= x)
{
if (ti >= pre[x]-(a[flag].r-a[flag].l))
{
return 1;
}
else
{
return 0;
}
}
else
{
if (ti >= pre[x])
{
return 1;
}
else
{
return 0;
}
}
}
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; // 若l = mid,则需要+1
if (check(mid))
l = mid;
else
r = mid - 1;
}
return l;
}
void solve()
{
int n, m;
cin >> n >> m;
int summax = 0;
int summin = 0;
int sumval = 0;
int ans = 0, t = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i].w >> a[i].l >> a[i].r;
summax+=a[i].r;
summin+=a[i].l;
sumval += a[i].r*a[i].w;
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
ans += a[i].w * a[i].l;
t += a[i].l;
}
for (int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1] + (a[i].r - a[i].l);
val[i] = val[i - 1] + (a[i].r - a[i].l) * a[i].w;
}
// for (int i = 1; i <= n; i++)
// {
// cout << pre[i] << " ";
// }
// cout << endl;
// for (int i = 1; i <= n; i++)
// {
// cout << val[i] << " ";
// }
// cout << endl;
int preans = ans;
// cout<<ans<<endl;
for (int i = 1; i <= n; i++)
{
int tt = t - a[i].l;
int res = preans - a[i].w * a[i].l;
ti = m - tt;
ans = max(ans, res + (ti * a[i].w));
//cout << ans << endl;
int l = 1, r = n;
flag = i;
int sumi = summax - a[i].r;
if(sumi-(summin-a[i].l)<ti){
res = sumval - a[i].r*a[i].w;
int mu = ti - (sumi-(summin-a[i].l));
res += mu*a[i].w;
ans = max(ans,res);
continue;
}
int lp = bsearch_2(l, r);
//cout << lp << " "<<i<<endl;
int lef ;//= ti - pre[lp];
if(lp>=i){
res += val[lp]-(val[i]-val[i-1]);
lef= ti -(pre[lp]-(pre[i]-pre[i-1]));
}else{
res += val[lp];
lef = ti-pre[lp];
}
if (lef > 0)
{
res += a[lp + 1].w * lef;
}
ans = max(ans, res);
//cout << ans << endl;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5708kb
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: 5716kb
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:
36099279
result:
wrong answer 1st lines differ - expected: '35204500', found: '36099279'