QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#790263 | #9529. Farm Management | iim76 | WA | 0ms | 3772kb | C++14 | 1.6kb | 2024-11-28 09:17:03 | 2024-11-28 09:17:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node{
int w, l, r;
bool operator<(const node & other)const{
return w < other.w;
}
};
void solve(){
int n;
ll m;
cin >> n >> m;
ll t = m;
vector<node> crops(n + 1);
for(int i = 1; i <= n; i++){
cin >> crops[i].w >> crops[i].l >> crops[i].r;
}
sort(crops.begin() + 1, crops.end());
vector<ll> prel(n + 5), prewl(n + 5), prelr(n + 5), prewlr(n + 5);
for(int i = 1; i <= n; i++){
prel[i] = prel[i - 1] + crops[i].l;
prewl[i] = prewl[i - 1] + crops[i].l * crops[i].w;
prelr[i] = prelr[i - 1] + crops[i].r - crops[i].l;
prewlr[i] = prewlr[i - 1] + (crops[i].r - crops[i].l) * crops[i].w;
}
ll ans = prewl[n];
t -= prel[n];
//prelr[n] - prelr [l] <= m
int p = lower_bound(prelr.begin() + 1, prelr.begin() + n + 1, prelr[n] - t) - prelr.begin();
t -= prelr[n] - prelr[p];
ans += prewlr[n] - prewlr[p];
ans += t * crops[p].w;
for(int i = 1; i <= n; i++){
ll s = m;
s -= prel[n];
ll res = prewl[n];
s += crops[i].l;
res -= crops[i].l * crops[i].w;
//prelr[n] - prelr[l] <= s
//假如多开数组避免特判,则要注意开始和结束位置
int p1 = lower_bound(prelr.begin() + i + 1, prelr.begin() + n + 1, prelr[n] - s) - prelr.begin();
res += prewlr[n] - prewlr[p1];
//cout << res << endl;
s -= prelr[n] - prelr[p1];
res += s * crops[p1].w;
ans = max(ans, res);
}
cout << ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
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: 3540kb
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:
42187156
result:
wrong answer 1st lines differ - expected: '35204500', found: '42187156'