QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#727274#9529. Farm ManagementxuzhihaodedieWA 1ms7700kbC++141.6kb2024-11-09 12:26:142024-11-09 12:26:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 12:26:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7700kb
  • [2024-11-09 12:26:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
#define PII pair<int,int>
//#define endl "\n"
#define lson 2*p
#define rson 2*p+1
const int N=2e5+10;
const int mod=998244353;
int l[N],r[N],w[N],id[N];
bool cmp(int x,int y) {
	return w[x]<w[y];
}
void solve() {
	int n,m;
	cin>>n>>m;
	int res=0,ans=0;
	int remain=m;
	for(int i=1;i<=n;i++) {
		cin>>w[i]>>l[i]>>r[i],res+=l[i]*w[i];
		remain-=l[i];
		id[i]=i;
	}
	sort(id+1,id+n+1,cmp);
	vector<int> pre(n+10,0),suf(n+10,0);
	vector<int> sufval(n+10,0);
	for(int i=1;i<=n;i++) {
		int p=id[i];
		pre[i]=pre[i-1]+r[p]-l[p];
	}
	for(int i=n;i>=1;i--) {
		int p=id[i];
		suf[i]=suf[i+1]+r[p]-l[p];
		sufval[i]=sufval[i+1]+(r[p]-l[p])*w[p];
	}
	for(int i=1;i<=n;i++) {
		int j=id[i];
		remain+=l[j];
		int ret=res-l[j]*w[j];
		int L=1,R=n,req=0;
		while(L<=R) {
			int mid=L+R>>1;
			int val=suf[mid];
			if(mid<=i) val=val+m-r[j];
 			if(remain>=val) req=mid,R=mid-1;
			else L=mid+1;
		}
		if(!req) {
			ans=max(ans,ret+(remain)*w[id[n]]);
		} else {
			ret+=sufval[req];
			int val=suf[req];
			if(req<=i) val+=m-r[j],ret+=w[j]*(m-r[j])+l[j]*w[j];
			if(req>1) {
				req--;
				int remain1=remain-val;
				remain1=max(0ll,remain1);
				if(req==i) {
					ret+=min(remain1,m-(r[j]-l[j]))*w[j];
				} else {
					j=id[req];
					ret+=min(remain1,r[j]-l[j])*w[j];
				}
			}
			ans=max(ans,ret);
		}
		remain-=l[j];
	}
	cout<<ans<<endl;
}
signed main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0),cout.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: 1ms
memory: 7700kb

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: 7688kb

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:

36577555

result:

wrong answer 1st lines differ - expected: '35204500', found: '36577555'