QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694218 | #9529. Farm Management | crychic# | WA | 0ms | 3552kb | C++17 | 1.7kb | 2024-10-31 17:29:21 | 2024-10-31 17:29:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void solve() {
ll n,m;
cin >> n >> m;
vector<array<ll,3>> a(n + 1);
for(int i = 1;i <= n;i ++){
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
sort(a.begin() + 1,a.end());
vector<ll> preL(n + 2),sufR(n + 2),preLw(n + 2),sufRw(n + 2);
for(int i = 1;i <= n;i ++){
preL[i] = preL[i - 1] + a[i][1];
preLw[i] = preLw[i - 1] + a[i][0] * a[i][1];
}
sufRw[n] = a[n][0] * a[n][2];
sufR[n] = a[n][2];
for(int i = n - 1;i >= 1;i --){
sufR[i] = sufR[i + 1] + a[i][2];
sufRw[i] = sufRw[i + 1] + a[i][0] * a[i][2];
}
ll ans = 0;
for(int i = 1;i <= n;i ++){
ll tmp = preL[i - 1] + sufR[i + 1];
if(tmp <= m){
ans = max(ans,preLw[i - 1] + sufRw[i + 1] + a[i][0] * (m - tmp));
}else {
int l = 1, r = n;
while(l + 1 < r){
int mid = l + r >> 1;
ll res = preL[mid] + sufR[mid + 1] - a[i][1];
if(res <= m)l = mid;
else r = mid;
}
ll cnt = m - (preL[l] + sufR[l + 1] - a[i][1]);
// cout << i << ' ' << l << ' ' << cnt << '\n';
// cout <<
// assert(cnt >= 0 && cnt < a[i][2] - a[i][1]);
ll ress = preLw[l] + sufRw[l + 1] - a[i][0] * a[i][1] + cnt * a[l][0];
ans = max(ans,ress);
}
}
cout << ans << '\n';
// for(int i = 1;i <= n;i ++)
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;b
while(t -- ) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3496kb
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: 3552kb
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:
44007019
result:
wrong answer 1st lines differ - expected: '35204500', found: '44007019'