QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#741386 | #9529. Farm Management | zxcdxw | WA | 0ms | 3784kb | C++14 | 1.6kb | 2024-11-13 14:15:19 | 2024-11-13 14:15:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define lowbit(x) (x)&(-x)
#define int long long
//#define double long double
const int N = 1e6 + 5;
const ll base = 131;
const ll mod = 998244353;
struct syz{
int a,b,c;
syz(){}
syz(int aa,int bb,int cc):a(aa),b(bb),c(cc)
{}
bool operator <(syz x){
if(this->a==x.a){
return this->b<x.b;
}
return this->a>x.a;
}
};
void solve() {
int n,m;
cin>>n>>m;
vector<syz>w(n+1);
for(int i=1;i<=n;++i) cin>>w[i].a>>w[i].b>>w[i].c;
sort(w.begin()+1,w.end());
vector<int>pre(n+1),presum(n+1);
for(int i=1;i<=n;++i) pre[i]=pre[i-1]+w[i].c-w[i].b,presum[i]=presum[i-1]+(w[i].c-w[i].b)*w[i].a;
ll ma=0,sum=0,Sum=0;
for(int i=1;i<=n;++i){
sum+=w[i].b;
Sum+=w[i].b*w[i].a;
}
ma=max(ma,Sum+(m-sum)*w[1].a);
for(int i=n;i>=1;--i){
//ma=max(ma,Sum+(m-sum)*w[i].a);
int res=m-sum+w[i].b;
if(res<pre[i-1]){
auto now=upper_bound(pre.begin()+1,pre.end(),res)-pre.begin()-1;
ma=max(ma,Sum-w[i].b*w[i].a+presum[now]+(res-pre[now])*w[i].a);
}
else {
int rest=res-pre[i-1];
ma=max(ma,Sum-w[i].b*w[i].a+rest*w[i].a+presum[i-1]);
}
// auto now=upper_bound(pre.begin()+1,pre.end(),res)-pre.begin()-1;
// ma=max(ma,Sum-w[i].b*w[i].a+presum[now]+(res-pre[now])*w[i].a);
}
cout<<ma<<'\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
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: 3740kb
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'