QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692070 | #9529. Farm Management | wangshengzhe# | WA | 1ms | 5700kb | C++14 | 1.7kb | 2024-10-31 13:45:04 | 2024-10-31 13:45:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ll = long long;
const int N = 2E5 + 10;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double ef = 1e-12;
const double PI = acos(-1);
#define rep(i,a,b) for(int i = a;i<=b;i++)
#define pre(i,a,b) for(int i = a;i>=b;i--)
#define int long long
int n, m;
struct node {
int le, ri;
int w;
};
node p[100005];
node qian[100005], ho[100005];
bool cmp(node a, node b)
{
return a.w < b.w;
}
int find1(int le, int ri, int tar)
{
while (le < ri)
{
int mid = (le + ri) >> 1;
if (ho[mid].ri <= tar) ri = mid;
else le = mid + 1;
}
return le;
}
void solve()
{
cin >> n >> m;
rep(i, 1, n) {
cin >> p[i].w >> p[i].le >> p[i].ri;
}
sort(p + 1, p + n + 1, cmp);
rep(i, 1, n) {
qian[i].le = qian[i - 1].le + p[i].le;
qian[i].w = qian[i - 1].w + p[i].w * p[i].le;
}
pre(i, n, 1) {
ho[i].ri = ho[i + 1].ri + p[i].ri;
ho[i].w = ho[i + 1].w + p[i].w * p[i].ri;
}
int ans = 0;
rep(i, 1, n)
{
int pp = find1(i + 1, n + 1, m - qian[i - 1].le);
int an;
if (pp - 2 >= i) an = ho[pp].w + qian[pp - 2].w - p[i].w * p[i].le + (m - qian[pp - 2].le - ho[pp].ri + p[i].le) * p[pp].w;
else an = ho[pp].w + qian[pp - 2].w + (m - qian[pp - 2].le - ho[pp].ri) * p[pp].w;
ans = max(ans, an);
}
pre(i, n, 1)
{
int an = qian[i - 1].w + ho[i + 1].w + (m - qian[i - 1].le - ho[i + 1].ri) * p[i].w;
ans = max(ans, an);
}
cout << ans << endl;
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5628kb
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: 5700kb
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'