QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#757807 | #9529. Farm Management | Cyan_Ghost | WA | 1ms | 3616kb | C++14 | 1.1kb | 2024-11-17 13:44:09 | 2024-11-17 13:44:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 101;
int p[N], v[N];
struct node {
int w, l, r, val;
} a[N];
bool cmp(node u, node v) {
if (u.w <= v.w) return true;
else return false;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
int all = 0, tim = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i].w >> a[i].l >> a[i].r;
a[i].val = a[i].w * (a[i].r - a[i].l); // 可以多的贡献
all += a[i].w * a[i].l;
tim += a[i].l;
}
sort(a + 1, a + n + 1, cmp);
for (int i = n; i >= 1; --i) {
p[i] = p[i + 1] + a[i].r - a[i].l; // 可以做的时间
v[i] = v[i + 1] + a[i].val; // 可以多的贡献
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
int now = all - a[i].w * a[i].l, t = m - tim + a[i].l;
int l = i + 1, r = n, k = n + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (p[mid] <= t) r = mid - 1, k = mid;
else l = mid + 1;
}
now += v[k], t -= p[k];
k -= 1;
now += t * a[i].w;
ans = max(ans, now);
}
cout << ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
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:
34859047
result:
wrong answer 1st lines differ - expected: '35204500', found: '34859047'