QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#691928 | #9529. Farm Management | galiyuu | WA | 1ms | 5672kb | C++14 | 1.3kb | 2024-10-31 13:27:48 | 2024-10-31 13:27:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define endl '\n'
#define SZ(x) ((int)(x).size())
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
mt19937 mrand(random_device{}());
int rnd(int x) {return mrand()%x;}
const ll mod=998244353;
// head
const int N=1e5+10;
ll n,m;
ll sa[N],w[N],t,aw;
array<ll,3> ty[N];
void solve() {
cin>>n>>m;
rep(i,1,n+1) {
cin>>ty[i][0]>>ty[i][1]>>ty[i][2];
ty[i][2]-=ty[i][1];
t+=ty[i][1],aw+=ty[i][0]*ty[i][1];
}
sort(ty+1,ty+n+1,[&](array<ll,3> a,array<ll,3> b){
return a[0]>b[0];
});
rep(i,1,n+1) {
sa[i]=ty[i][2];
w[i]=ty[i][2]*ty[i][0];
sa[i]+=sa[i-1],w[i]+=w[i-1];
}
ll ans=0;
rep(i,1,n+1) {
ll tmp=m-t+ty[i][1];
ll nw=aw-ty[i][1]*ty[i][0];
auto it=lower_bound(sa+1,sa+n+1,tmp)-sa;
if (it>i) {
nw+=w[it-1],tmp-=sa[it-1];
nw+=tmp*ty[i][0];
} else {
nw+=w[it-1],tmp-=sa[it-1];
nw+=tmp*ty[it][0];
}
ans=max(ans,nw);
}
cout<<ans<<endl;
}
int tc;
signed main() {
ios::sync_with_stdio(0);
tc=1;
while (tc--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5604kb
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: 0
Accepted
time: 1ms
memory: 5580kb
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:
35204500
result:
ok single line: '35204500'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5672kb
input:
15 32 835418 2 3 178262 1 3 527643 2 2 519710 1 1 774544 3 3 82312 1 1 808199 1 1 809396 1 3 255882 1 3 80467 1 3 874973 1 3 813965 1 2 198275 1 2 152356 1 3 802055 1 1
output:
17015002
result:
wrong answer 1st lines differ - expected: '22000255', found: '17015002'