QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694344 | #9529. Farm Management | crychic# | WA | 0ms | 3616kb | C++23 | 1.5kb | 2024-10-31 17:45:09 | 2024-10-31 17:45:20 |
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 + 10,0),sufR(n + 10,0),preLw(n + 10,0),sufRw(n + 10,0);
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 = sufR[i + 1] + preL[i - 1];
if(tmp <= m){
ans = max(ans,preLw[i - 1] + sufRw[i + 1] + (m - tmp) * a[i][0]);
}else {
ll need = tmp - m;
ll res = preLw[i - 1] + sufRw[i + 1];
for(int j = i + 1;i <= n;i ++){
ll sub = a[j][2] - a[j][1];
sub = min(sub,need);
res -= sub * a[j][0];
need -= sub;
}
ans = max(ans,res);
}
}
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: 3608kb
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: 3616kb
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:
43038513
result:
wrong answer 1st lines differ - expected: '35204500', found: '43038513'